题意：有n个点， p条路，每条道路有个花费Li， 然后现在要建一条1-n的路线，然后可以选k条道路免费， 然后可以在剩下的道路中选择价格最高的边支付费用， 求这个答案最小。
题解：
二分答案。
每次check过程中， 一条边的花费 <= mid 则 路径长度为0，否者路径长度为1。
然后 求 到n的点之后长度<=k。
然后就是bfs的过程中。 如果这条边是0， 那么从前入队， 否者从后入队。
代码：
#include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<map> #include<iostream> #include<cstring> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 1e5 + 100; int n, p, k; int fu[N], fv[N], fw[N]; vector<int> vc[N][2]; int d[N], vis[N]; deque<int> q; bool check(int val){ for(int i = 1; i <= n; ++i){ vc[i][0].clear(); vc[i][1].clear(); d[i] = inf; vis[i] = 0; } for(int i = 1; i <= p; ++i){ if(fw[i] <= val) { vc[fu[i]][0].pb(fv[i]); vc[fv[i]][0].pb(fu[i]); } else { vc[fu[i]][1].pb(fv[i]); vc[fv[i]][1].pb(fu[i]); } } q.pb(1); d[1] = 0; while(!q.empty()){ int x = q.front(); q.pop_front(); vis[x] = 1; for(int i = 0; i < vc[x][0].size(); ++i){ int v = vc[x][0][i]; if(d[v] == inf){ d[v] = d[x]; q.push_front(v); } } for(int i = 0; i < vc[x][1].size(); ++i){ int v = vc[x][1][i]; if(d[v] == inf){ d[v] = d[x] + 1; q.push_back(v); } } } // cout << d[n] << endl; return d[n] <= k; } int main(){ scanf("%d%d%d", &n, &p, &k); for(int i = 1; i <= p; ++i) scanf("%d%d%d", &fu[i], &fv[i], &fw[i]); int l = 0, r = 1000000; // check(1); while(l <= r){ int mid = l+r >> 1; if(!check(mid)) l = mid+1; else r = mid - 1; } if(l > 1000000) l = -1; printf("%d ", l); return 0; } /* 5 4 4 1 2 1 2 3 1 3 4 1 4 5 999999 */