题面
大意：在加权无向图上求出一条从 (1) 号结点到 (N) 号结点的路径，使路径上第 (K + 1) 大的边权尽量小。
思路：
由于我们只能直接求最短路，不能记录过程中的具体的边——那样会特别麻烦
所以，我们就尝试着去想更优的办法
题目中所说，能够免去 (K) 条边的费用，那么对于要建设的边中，肯定免去费用最大 $K $ 条边更优
我们关注的应该是第 (K+1) 大边的边权，因为其他边权大于这条边边权的边都会被略去
这条边可以枚举吗？
似乎不行，枚举的复杂度还要在最短路的基础上，乘上一个 (M) ，不就TLE（Time Limit Enough）了吗……
那么——对于这个边的边权，能不能二分呢？
首先，二分需要满足单调性
题目中，这条第 (K+1) 大的边边权越小，能够满足的情况越少，反之亦然
因此我们可以使用二分的方法来查找答案
怎么判断满足或不满足
对于边权大于 (mid) 的边，我们改变它的边权为1，否则为0，然后再跑最短路，这样得出来的结果应该是从 (1) 号结点到 $N $ 号结点至少要有几条大于 (mid) 的边，然后与 (K) 比较，小于 (K) 则满足，否则不满足
Code：
#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define M 10010
#define N 1010
using namespace std;
struct node{
int to,cost;
int nxt;
node(int a,int b):to(a),cost(b){ }
node(){ }
}b[M<<1];
int head[N],d[N],vis[N];
int n,m,res,t,ans=INF;//初值一样要为INF
int read()
{
int s=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
s=(s<<1)+(s<<3)+c-'0';
c=getchar();
}
return s;
}
void add(int x,int y,int cost)//建边，正反一起
{
b[++t]=node(y,cost);
b[t].nxt=head[x];
head[x]=t;
b[++t]=node(x,cost);
b[t].nxt=head[y];
head[y]=t;
return;
}
bool BFS(int k)//好吧，这里不算严格的最短路，因为边权变成了0和1，可以直接宽搜搞定，但是下面的程序，
{//明明是一个真SPFA，假宽搜
int i,to,cur,cost;
for(i=1;i<=n;i++)
{
d[i]=INF;
vis[i]=0;
}
queue<int>p;
p.push(1);
vis[1]=1;
d[1]=0;
while(!p.empty())
{
cur=p.front();p.pop();
vis[cur]=0;
for(i=head[cur];i;i=b[i].nxt)
{
to=b[i].to;
cost=d[cur]+(b[i].cost>k);//处理边权
if(cost<d[to])
{
d[to]=cost;
if(!vis[to])
{
vis[to]=1;
p.push(to);
}
}
}
}
if(d[n]<=res)//判断
return 1;
return 0;
}
int main()
{
int i;
int x,y,cost;
int l,r,mid;
n=read();m=read();res=read();
l=r=0;
for(i=1;i<=m;i++)
{
x=read();y=read();cost=read();
add(x,y,cost);//建边，注意是双向的
r=max(r,cost);//r的上限，可以自己赋为1e6，这是题目中给的最大值
}
while(l<=r)
{
mid=(l+r)>>1;
if(BFS(mid))//判断
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
if(ans==INF)//初值应该为INF，不能为0，因为有可能电信公司比较大方，免费之类的——给我多好
ans=-1;
printf("%d",ans);
return 0;
}
另外提供一个比较high的评测
在洛谷过了，这里不一定过哦！