POJ 3662 Telephone Lines

解を二分探索 + ダイクストラ

// compile in C++11. use -std=c++11.
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>


using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

struct Edge{
    int to,cost;
    Edge(int to_,int cost_)
        : to(to_),cost(cost_) {
    }
};

int mydijkstra(const int start,const int goal,const int u,
             const vector<vector<Edge> > &graph){
    typedef pair<int,int> pii;
    int N = graph.size();
    vector<char> visited(N,false);
    // cost where
    priority_queue<pii,vector<pii>,greater<pii> > que;
    que.push(make_pair(0,start));
    while(not que.empty()){
        int cost,where;
        cost = que.top().first;
        where = que.top().second;
        que.pop();
        if(visited[where]) continue;
        if(where == goal) return cost;
        visited[where] = true;
        for(int j=0;j<(int)graph[where].size();j++){
            if(graph[where][j].cost <= u){
                que.push(make_pair(cost,graph[where][j].to));
            }else{
                que.push(make_pair(1+cost,graph[where][j].to));
            }

        }
    }
    return -1;
}

int solve(const int N,const int P,const int K,
          const vector<int> &A,
          const vector<int> &B,
          const vector<int> &L){
    const int INF = 1000001;
    int lower = 0;
    int upper = INF;

    // いくら払うかで二分探索。
    //  K本ただで貰える。 -> K+1本目の枝
    vector<vector<Edge> > graph(N);
    repeat(i,P){
        graph[A[i]].push_back(Edge(B[i],L[i]));
        graph[B[i]].push_back(Edge(A[i],L[i]));
    }

    repeat(bin_search,20){
        int mid = (lower+upper)/2;
        int d = mydijkstra(0,N-1,mid,graph);
        // ok
        if(0 <= d and d <= K){
            upper = mid;
        }else{
            lower = mid;
        }
    }
    if(upper >= INF) return -1;
    return upper;
}

int main(){
    int N,P,K;
    cin >> N >> P >> K;
    vector<int> A(P),B(P),L(P);
    repeat(i,P){
        scanf("%d %d %d",&A[i],&B[i],&L[i]);
        A[i]--;
        B[i]--;
    }
    cout << solve(N,P,K,A,B,L) << endl;
    return 0;
}