POJ 3662: Telephone Lines

概要

N頂点，辺P本のグラフが与えられる．K本の辺は無料で使うことができ，それ以上使うとK本からはみ出た辺の中での最大の長さだけの料金が発生する．
頂点1から頂点Nまでの経路をできるだけ安い料金で実現したい．

解法

料金（辺の長さの最大値）について二分探索．料金をdと仮定したとき，dより長い辺をK本以下使って1からNへの経路をつくれるかを判定する．判定にはDijkstraを利用．

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
bool operator<(const Edge &a, const Edge &b){
    return a.weight > b.weight;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

const int INF = 1000000;

int N, P, K;
int d[1010];
bool visited[1010];
bool C(Graph &g, int L) {
    priority_queue<Edge> Q;
    for(int i = 0; i < N; ++i) d[i] = INF;
    memset(visited, 0, sizeof(visited));
    
    d[0] = 0;
    Q.push(Edge(-1, 0, 0));
    while(!Q.empty()){
        int v = Q.top().to;
        int cnt = Q.top().weight;
        Q.pop();
        if(visited[v]) continue;
        visited[v] = true;
        if(v == N-1) return cnt <= K;
        EACH(i, g[v]){
            int ncnt = cnt;
            if(i->weight > L) ncnt++;
            if(d[i->to] > ncnt){
                d[i->to] = ncnt;
                Q.push(Edge(i->from, i->to, ncnt));
            }
        }
    }
    return false;
}
main(){
    scanf("%d%d%d", &N, &P, &K);
    Graph g(N);
    for(int i = 0; i < P; ++i){
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        --a; --b;
        g[a].push_back(Edge(a, b, l));
        g[b].push_back(Edge(b, a, l));
    }
    int lb = -1, ub = 1000010;
    while(ub - lb > 1){
        int mid = (lb + ub) / 2;
        // printf(">%d\n", mid);
        if(C(g, mid)){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%d\n", ub > 1000000 ? -1: ub);
}