#10074. 「一本通 3.2 例 3」架设电话线

在加权无向图上求出一条从 1 号结点到 N 号结点的路径，使路径上第 K + 1 大的边权尽量小

二分答案md, 判断1~n是否存在一条路径，花费不超过md

把w<=md 的边看作0，否则看作1，求1到n 的最短路，看 dis[n]<=md

#include <bits/stdc++.h>
using namespace std ; 
 const int N=5000,M=1e4+3;
 #define int long long 
 int n,m,K;
 int all,nxt[M],go[M],hd[N],vis[N],w[M];
 int b[N],d[N];
 
 struct T{
     int y,z;
     T(int y0,int z0){
         y=y0,z=z0;
     }
     bool operator<(T a)const{
         return z>a.z;
     }
 };
 
 void add(int x,int y,int z){
     go[++all]=y;
     w[all]=z,nxt[all]=hd[x],hd[x]=all;
 }
 
 int chk(int md){
     int i,x,y,z;
     priority_queue<T>q;
     memset(d,0x3f3f3f3f,sizeof d); d[1]=0;
     memset(b,0,sizeof b);
     q.push(T(1,0));
     
     while(q.empty()==0){
         x=q.top().y,q.pop(); if(b[x]) continue;
         b[x]=1;
         for(i=hd[x];i;i=nxt[i]){
             y=go[i],z=(w[i]>md);
              
             if(d[x]+z<d[y]){
                 d[y]=d[x]+z; q.push(T(y,d[y]));
             }
         }
     }
     return d[n]<=K;
 }
 
 main(){
     int l=0,r=0;
     int i,x,y,z;
     cin>>n>>m>>K;
     for(i=1;i<=m;i++) 
     cin>>x>>y>>z,add(x,y,z),add(y,x,z),r=max(r,z);
     
     int ans=-1;
     while(l<=r){
         int md=(l+r)/2;
         if(chk(md)) r=md-1,ans=md; else l=md+1;
     }
     cout<<ans;
 }