题意：
给一个2e4带正边权的图，可以免费k个边，一条路径的花费为路径上边权最大值，问你1到n的最小花费
思路：
对于一个x，我们如果将大于等于x的边权全部免费，那么至少需要免费的边的数量就是
“设大于等于x的边权的边长为1，其余为0，起点到终点的最短路”
然后如果这个得到的最短路，也就是我们所需要免费的边数小于等于k的话，就可以满足题意了(check)
思考一下可以发现对于任何条件，都存在某一个p，当x取[p, inf]的任意值时，都是可以满足题意的
于是我们就可以二分x并check了
得到p之后跑一遍最短路上的最大值，就是答案了（我每次check成功后记录了一次pre）
这题要注意不连通时候的情况输出-1
update：今天仔细想了一下，其实二分的就是ans+1，最后只需要输出max(ans-1,0)就是答案
然后二分+最短路也只能用于这种路径上边权最大值为费用的题了
代码：
有点像西安邀请赛的二分最短路啊
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
//#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f; const db pi = acos(-1.0); int n, m, k;
int dist[maxn];
struct node{
int id, d;
node(){}
node(int a,int b) {id = a; d = b;}
bool operator < (const node & a)const{
if(d == a.d) return id > a.id;
else return d > a.d;
}
};
vector<node>e[maxn];
PI pre[maxn];
PI tpre[maxn];
void dijkstra(int s, int ki){
for(int i = ; i <= n; i++) dist[i] = inf;//往往不够大 dist[s] = ;
priority_queue<node>q;
q.push(node(s, dist[s]));
while(!q.empty()){
node top = q.top();
q.pop();
if(top.d != dist[top.id]) continue;
for(int i = ; i < (int)e[top.id].size(); i++){
node x = e[top.id][i];
int d=;
if(x.d>=ki)d=;
if(dist[x.id] > top.d + d){
pre[x.id]=make_pair(top.id,x.d);
dist[x.id] = top.d + d;
q.push(node(x.id, dist[x.id]));
}
}
}
return;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
int ans = -inf;
int l,r;
for(int i = ; i <= m; i++){
int x ,y,w;
scanf("%d %d %d", &x, &y, &w);
e[x].pb(node(y,w));
e[y].pb(node(x,w));
}
l=;r=+;
while(l<=r){
int mid = (l+r)>>;
dijkstra(,mid);
//printf("--%d %d %d ==%d\n",l,r,mid,dist[n]);
if(dist[n]<=k){
for(int i = ; i <= n; i++){
tpre[i]=pre[i];
}
r=mid-;
ans=mid;
}
else l=mid+;
}
//printf("%d\n",ans);
if(ans==-inf)return printf("-1"),;
int res = ;
for(int i = n; i != ; i = tpre[i].fst){
//printf("--%d %d %d\n",i, pre[i].fst, pre[i].sc);
int x = tpre[i].sc;
if(x>=ans)continue;
res = max(res, x);
}
printf("%d",res);
return ;
}
/*
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 3 1
1 2 2
1 3 5
2 3 3
*/