题意：
给定一个无向有权图，权值代表修建电线需要的花费，公司给报销K条线，这个人需要付款剩下的线路中花费最大的那个线路。
题解：
最短路问题，只不过这时候的最短路不是让求最短的距离了，而是给定一个花费X，是否有一条通路能够满足，恰好有K+1条路满足>=X，这个X就是可行解。二分去求最小的可行解就可以了！
所以这个时候d[]数组放最短距离已经没有任何意义了，而是放到达终点>=X的边数最少有多少条。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>using namespace std;
const int maxl=1000000;
int d[1000+5];//“最短距离”，记录大于等于mid的有多少条边！struct edge{int to,cost;};
vector<edge>G[1000+5];//边typedef pair<int,int>P;//最短路径，顶点编号int V,E,K;//Dijkstra算法。收进来不属于集合的点的时候，不是更新最短路径了，而是更新到达此点共需要>=mid
//的边多少条！bool C(int mid)
{priority_queue<P,vector<P>,greater<P> >que;fill(d,d+V+2,0x3f3f3f3f);d[1]=0;//起点que.push(P(0,1));while(que.size()){P p=que.top();que.pop();int v=p.second;if(d[v]<p.first)continue;for(int i=0;i<G[v].size();i++){edge e=G[v][i];int new_d=d[v]+(e.cost>=mid?1:0);//记录大于等于mid的。if(d[e.to]>new_d){d[e.to]=new_d;que.push(P(d[e.to],e.to));}}}return d[V]>=K+1;//k+1这个边界是最后的可行解！// 因为>=mid有K+1个说明mid右边刚好有K个免费的，此时的mid就是最优解。//所以满足这个条件的mid即为答案。
}int main()
{cin>>V>>E>>K;for(int i=1;i<=E;i++){int from,to,cost;cin>>from>>to>>cost;G[from].push_back(edge{to,cost});G[to].push_back(edge{from,cost});}int lb=0,ub=maxl+2;while(ub-lb>1){int mid=(ub+lb)>>1;if(C(mid))lb=mid;else ub=mid;}
cout<<(lb>maxl?-1:lb)<<endl;}