题目描述
在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。
现在，农场主希望对通信线路进行升级，其中升级第i条电缆需要花费Li。
电话公司正在举行优惠活动。农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱可以完成升级。
输入格式
第 1 行：三个整数 N，P，K。
第 2..P+1 行：第 i+1 行包含三个整数 Ai,Bi,Li。
输出格式
包含一个整数表示最少花费。
若 1号基站与 N 号基站之间不存在路径，则输出 −1。
数据范围
0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000
输入样例
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样例
4
思路：要去掉k条边，当然是花费最高的几条，然后求剩下的边中，最大权值的最小。
求最大值的最小，最小值的最大，这不是二分答案的标志嘛？
二分花费（每条边）。
check：
1.spfa求，到达目标时 ，所走的路径中，要去掉的边的最小次数。（即，最少使用的魔法次数）
2.每个节点的dist数组中存的是到达这个节点所使用的最少魔法次数。（最短路思路）
3.如果，碰到一条边的权值大于mid了，就将该边去掉（即，使用的魔法次数+1）
4.最后，如果，目标点存的使用的魔法次数大于k了，说明这个花费不满足情况。如果满足情况，mid尽量往左走，让花费尽量小（因为要求最小花费）
C++ code（详细注释）:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
//题目转化为，求一个从1到n的路径，除掉k条边之后，剩余的最大边权最小；
const int N=20010;
int n,m,k,e[N],ne[N],h[N],w[N],idx;
int dist[N],f[N];
void add(int x,int y,int z){
e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
//判断的是，能否每条路径花费都不超过mid到达终点
//思路：如果碰到一个边的权值大于mid了，那就使用一次魔法，将该边免费
int check(int mid) //spfa算法求，到达终点时，使用最少魔法的路径
{
memset(dist,0x3f,sizeof dist); //dist里存的是走过的权值大于mid的边的个数
dist[1]=0;
queue<int> que;
que.push(1);
f[1]=true;
while(que.size())
{
int x=que.front();
que.pop();
f[x]=false;
for(int i=h[x];i!=-1;i=ne[i]) //更新与其相连的节点
{
int t=0;
int tx=e[i];
if(w[i]>mid) t=1; //若边的权值大于mid了，说明要让这条边免费（即，用一次魔法）。然后dist[x]要+1再判断是否能更新
if(dist[tx]>dist[x]+t) //能更新
{
dist[tx]=dist[x]+t;
if(!f[tx]){
f[tx]=true;
que.push(tx);
}
}
}
}
if(dist[n]==0x3f3f3f3f) return -1; //目标节点没被更新，说明没有路径能到达
else if(dist[n]<=k) return 1; //到达目标时，所用的魔法小于等于k，说明能满足条件：每条边的花费不超过mid，且不超过k条边免费
return 0; //不能满足要求
}
int main(){
cin>>n>>m>>k;
memset(h,-1,sizeof h);
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
int l=0,r=1000010;
while(l<r) //二分答案：最小花费
{
int mid=l+r>>1;
int t=check(mid);
if(t==1) r=mid; //满足条件，尽量往左来，
else if(t==0) l=mid+1; //不满足
else{ //不存在路径
cout<<-1; return 0;
}
}
cout<<l; //最终的l就是最小花费
return 0;
}
太好了