Telephone Lines (POJ 3662)

This questions combines graph theory and binary search methods. Given a connected graph, from a path from start node to end node you can drop K edges' costs. It is obviously that we should drop those with highest cost. The key to this problem is that, for edges left, the total cost is measured by one of the highest cost instead of the total cost.

So that we can using binary search to guess the highest possible single edge cost left and verify if we can drop exactly K edges in the shortest path while all edges dropped has greater cost than our guessed value. To achieve this, for a guessed cost C, we regard edges with cost C' > C to have cost 1 and other edges' cost to be zero. Then if the shortest path in the new graph is less than or equal to K, we know that it is possible to drop K edges in one of the path and let the highest cost in left edge is not greater than C. Or, the guessed C is not valid, we should increase our guess.

We use dijkstra algorithm to fast find the sortest path cost in the transformed graph and binary search to pick the lowest possible value C.

import java.io.*;
import java.util.*;

class Edge implements Comparable<Edge> {
    int u;
    int v;
    int cost;

    public Edge(int u, int v, int cost) {
        this.u = u;
        this.v = v;
        this.cost = cost;
    }

    public int compareTo(Edge b) {
        return this.cost - b.cost;
    }
}

public class TelephoneLines {
    private static int dijkstra(int N, int mid, List<List<Edge>> graph) {
        int[] dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        PriorityQueue<Edge> que = new PriorityQueue<Edge>();
        que.offer(new Edge(0, 0, 0));

        while (!que.isEmpty()) {
            Edge p = que.poll();
            if (dist[p.u] < p.cost) continue;

            for (Edge e : graph.get(p.u)) {
                int newd = p.cost + ((e.cost > mid) ? 1 : 0);
                if (dist[e.v] > newd) {
                    dist[e.v] = newd;
                    que.offer(new Edge(e.v, 0, dist[e.v]));
                }
            }
        }

        return dist[N - 1];
    }
    private static void solve(int N, int K, List<List<Edge>> graph) {
        int l = 0, u = 1000005;
        while (l <= u) {
            int mid = (l + u) / 2;
            if (dijkstra(N, mid, graph) <= K) u = mid - 1;
            else l = mid + 1;
        }
        if (l > 1000000)
            System.out.println(-1);
        else
            System.out.println(l);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str;
        str = in.readLine().split(" ");
        int N = Integer.parseInt(str[0]), P = Integer.parseInt(str[1]), K = Integer.parseInt(str[2]);
        ArrayList<List<Edge>> edges = new ArrayList<List<Edge>>(N);
        for (int i = 0; i < N; i++) {
            edges.add(new ArrayList<Edge>());
        }
        for (int i = 0; i < P; i++) {
            str = in.readLine().split(" ");
            int a = Integer.parseInt(str[0]) - 1, b = Integer.parseInt(str[1]) - 1, c = Integer.parseInt(str[2]);
            edges.get(a).add(new Edge(a, b, c));
            edges.get(b).add(new Edge(b, a, c));
        }
        solve(N, K, edges);
    }
}