二分一个长度，(count)dis[n]<=k
O(PlogNlogK)
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 }