问题抽象：
给定一张无向图，求出一条1~n的路径，使得路径中第k+1大的边权最小化。
算法描述：
二分答案。
对于二分的值mid，定义在所有1~n的路径中，满足权值大于mid的边的数量小于等于k者为合法路径。
当mid越大时，权值大于mid的边的数量必然非严格单调递减，故而合法路径的数量必然也非严格单调递减。
故而该问题满足如上单调性，二分答案的可行性成立。
因此，可将问题转化为判定：
对于给定的mid，是否存在一条路径，使该路径上的权值大于mid的边的数量小于等于k。
这个问题就非常好做了。只需把权值大于mid的边的权值视为1，其余边权值视为0，然后求解01最短路即可，复杂度是线性的。
最终整个算法的时间复杂度为O((N+M)logMAX_L)
参考代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 const int N=1e3+10,M=1e4+10; 7 struct Edge{ 8 int to,ne,w; 9 }edge[M<<1]; int idx; 10 int n,m,k; 11 int h[N]; 12 int dis[N],vis[N]; 13 14 void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;} 15 16 bool check(int mid) 17 { 18 memset(dis,0x3f,sizeof dis); 19 memset(vis,0,sizeof vis); 20 deque<int> q; 21 22 dis[1]=0; 23 q.push_front(1); 24 25 while(!q.empty()) 26 { 27 int p=q.front(); 28 q.pop_front(); 29 30 if(vis[p])continue; 31 vis[p]=1; 32 33 for(int i=h[p];~i;i=edge[i].ne) 34 { 35 int to=edge[i].to,w=edge[i].w>mid; 36 if(dis[to]>dis[p]+w) 37 { 38 dis[to]=dis[p]+w; 39 if(w)q.push_back(to); 40 else q.push_front(to); 41 } 42 } 43 } 44 45 return dis[n]<=k; 46 } 47 48 int main() 49 { 50 memset(h,-1,sizeof h); 51 scanf("%d%d%d",&n,&m,&k); 52 53 for(int i=1;i<=m;i++) 54 { 55 int u,v,w; 56 scanf("%d%d%d",&u,&v,&w); 57 add_edge(u,v,w); 58 add_edge(v,u,w); 59 } 60 61 int l=0,r=1e6+1; 62 while(l<r) 63 { 64 int mid=(l+r)>>1; 65 if(check(mid))r=mid; 66 else l=mid+1; 67 } 68 69 if(r==1e6+1)puts("-1"); 70 else printf("%d\n",r); 71 72 return 0; 73 }