题意简述：
在无向图上求出一条1~N的路径，使路径上第K+1大的边权最小。
解题思路：
本题可采用动态规划+SPFA，也可采用二分搜索，这里讲解二分搜索做法。我们知道，适用二分搜索的前提是答案具有单调性，本题符合该条件，于是我们可以把答案转化成：是否存在一种合法的升级方法，使花费不超过mid。 转化后我们仍需做一些改变，我们令价格大于mid的边，边权看为1，小于等于的看作0，于是我们只需求1~n的最短路是否超过k即可。这里check函数我们可以采用双端队列BFS方法实现，效率为O(N)，算法最终效率为O((N+P)log MAX_L) 需要注意的是二分搜索的边界条件，如何如何根据check返回值来收缩l和r，以及如何判断无解。
参考书目
《算法竞赛进阶指南》,李煜东,P328
代码示例
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1100;
const int M = 2*11000;
//邻接表存储无向图
int head[N],ver[M],edge[M],d[N],Next[M];
bool vis[N];
int tot,n,m,k;
deque<int> q;
void add(int x,int y,int z){
ver[++tot] = y,edge[tot] = z;
Next[tot] = head[x],head[x] = tot;
}
bool check(int mid){
//采用双端队列BFS来求1~n最短路径
memset(d,0x3f,sizeof d);
memset(vis,false,sizeof vis);
d[1] = 0;
q.push_back(1);
while(q.size()){
int x = q.front();q.pop_front();
if(vis[x]) continue;
vis[x] = true;
for(int i = head[x]; i;i = Next[i]){
int y = ver[i],z = edge[i] > mid ?1:0;
d[y] = min(d[y],d[x]+z);
if(z) q.push_back(y);
else q.push_front(y);
}
}
return d[n] <= k;
}
void solve(){
//二分搜索算法
int INF = 0x3f3f3f3f;
int l = 0,r = INF;
while(l < r){
int mid = (l+r)>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
if(l >= INF) puts("-1");
else printf("%d\n",l);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1,x,y,z;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
solve();
return 0;
}
