POJ3662 Telephone Lines

 1 #include <queue>
 2 #include <iostream> 
 3 using namespace std;
 4 const int INF=1e9,N=1e5+10;
 5 struct edge {
 6     int v,w;
 7     edge(int v,int w):v(v),w(w){}
 8     bool operator<(const edge &a)const{return w>a.w;}
 9 };
10 
11 vector<edge>g[N];
12 int n,m,k,dis[N],vis[N];
13 
14 bool ok(int limit) {
15     for(int i=1; i<=n; i++)dis[i]=INF,vis[i]=0;
16     priority_queue<edge>q;
17     dis[1]=0,q.push(edge(1,0));
18     while(!q.empty()) {
19         edge e=q.top();q.pop();
20         int u=e.v;
21         if(vis[u])continue;
22         vis[u]=1;
23         for(int i=0;i<g[u].size();i++) {
24             int&v=g[u][i].v;
25             int w=g[u][i].w>limit?1:0;
26             if(dis[v]>dis[u]+w) {
27                 dis[v]=dis[u]+w;
28                 q.push(edge(v,dis[v]));
29             }
30         }
31     }
32     return dis[n]<=k;
33 }
34 
35 int solve() {
36     int l=0,r=1e7,ans=-1;
37     while(l<=r) {
38         int mid=(l+r)>>1;
39         if(ok(mid))r=mid-1,ans=mid;
40         else l=mid+1;
41     }
42     return ans;
43 }
44 
45 int main() {
46     while(cin>>n>>m>>k) {
47         for(int i=1; i<=n; i++)g[i].clear();
48         for(int i=1; i<=m; i++) {
49             int u,v,w;
50             cin>>u>>v>>w;
51             g[u].push_back(edge(v,w));
52             g[v].push_back(edge(u,w));
53         }
54         cout<<solve()<<endl;
55     }
56     return 0;
57 }