看到有大佬们把这次考试的题都讲了一遍，见没有讲修复路线的，那我就来凑凑数吧。
仔细读题，我们可以发现，这题是一个极为明显的最短路，而“最长的最短”这句话又告诉我们是二分答案，所以基本确定就是 最短路与二分答案 了，理解题意之后发现这是一个 二分答案用最短路验证 。根据题目选择最短路的算法，发现用 dijkstra 及其堆优化或 SPFA 合适一些，这里选用 SPFA，用邻接表存图。
因为根据二分答案的套路，判断条件应该是
if(dis[n]<=k)return 1;else return 0;而在下面的判断中则应是
if(check(mid))r=mid;else l=mid;也就是说如果满足了就去尝试更小的。
这个也比较好理解（吧），不会的同学还是学学二分吧。
我们二分答案所枚举的是最长的最短，但如何用最短路来验证呢？
其实很简单，我们可以再建一个图，将图中所有长度大于mid的边全部长度设为1，小于等于mid的则设置为0,；
这么做就表示长度为1的如果要连接就必须要报销；因为HL十分抠门，所以需要把长的都留给保险公司报销。
接着，开始做单源最短路：dis[] 数组存各个节点到节点1的最短路径，开始初值为一个大数（如果是 mesmet 10的话为 168430090），用 SPFA（可以用 STL 库）来做一遍第二个图上的最短路，最后判断 dis[n] 与 k 的大小关系 return 即可，操作见上代码。因为题目想连接的是 1 号机与 n 号机，所以这里 dis[n] 所代表的是“当自己接的网线最长的最短为 mid 时连接到 n 号机最少报销的网线条数”，将这个与 k 比较即可验证这个二分了。
由于我是用SPFA且是邻接表存图，代码难免有些繁琐，对于读入存图上还是有一些可有可无的玩意，我仅是提供了一个思路而已 。
但我还是要献上我的代码：
#include<bits/stdc++.h> using namespace std; struct rode{ int x,y,t,next;//x表示b号机，t表示a号机，y表示网线长度，next表示下一个的地址 }e[25001]={},b[25001]={}; int dis[1001]={};//dis数组表示各个电脑到1号机的最短路径（最少报销数） int f[1001]={},l=0,r=1e8,len=0,n,p,k;//f数组的意义也与邻接表的储存有关，所以还是自行理解吧； bool che(int mid){ queue<int>q;//通过STL的队列来实现SPFA memset(dis,10,sizeof(dis));//赋初值，这里赋的值表示168430090 for(int i=1;i<=len;i++){ // if(e[i].y<168430090) 这句其实可有可无 if(e[i].y<=mid)b[i].y=0;//如果长度小于二分枚举的mid，则赋为0 else b[i].y=1;//否则赋为1，表示若要连接则需要报销 if(e[i].t==1)dis[e[i].x]=e[i].y;//先把与1号机有直接连线的赋上 } dis[1]=0;//自己到自己当然是0 bool p[1000001]={};//这个数组表示是否 走过 ; q.push(1);p[1]=1;//现将1号机入队，并标记为走过了 ; while(!q.empty()){//q.empty 表示判断队列是否为空，为空则返回0 int t=q.front();q.pop(); p[t]=0;//走过之后归零，思考为什么 for(int i=f[t];i;i=b[i].next)//遍历邻接表 if(b[i].y+dis[t]<dis[b[i].x]){//这个就是∨（箭头） dis[b[i].x]=dis[t]+b[i].y; //松弛操作了 if(p[b[i].x]==0){//若标记为没走过的则可以入队 q.push(b[i].x); p[b[i].x]=1;//标记为走过的 } } } if(dis[n]==168430090){//若点n还是原值没被更新过，则说明无法走到n号机，可以直接输出-1了 cout<<"-1"<<endl; exit(0); } if(dis[n]<=k)return 1;// 上面有解释 else return 0; } void ins(int x,int y,int z){//这个邻接表的储存方法可以百度或自行理解 e[++len].x=y; e[len].y=z; e[len].t=x; e[len].next=f[x]; b[len].x=y; //注意：e数组是原图，b数组是做最短路的图，b数组在这里不能给b[len].y赋值； b[len].t=x; b[len].next=f[x]; f[x]=len; } int main() { freopen("wire.in","r",stdin); freopen("wire.out","w",stdout); scanf("%d%d%d",&n,&p,&k); for(int i=1;i<=p;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z);//分别输入a号机，b号机，网线长度 ins(x,y,z);ins(y,x,z);//这是无向图，相当于两条有向边 } while(l+1<r){//这是保险的方法，退出循环之后再在下面判断一次 int mid=(l+r)>>1;//相当于int mid=(l+r)/2; if(che(mid))r=mid;//注意：这里是r=mid优先，else后面的是l else l=mid; } if(che(l))printf("%d",l);//退出后最后判一次来确定，若是弄不好则老是会差1 else printf("%d",r); fclose(stdin);fclose(stdout); return 0; }以上，是我去年写的。今天又写到这题，过来鞭尸。
槽也不吐了，去年写的太垃圾，现在补充：
数据范围可到 1e6 范围，将最短路换成搜索（Bfs）之类的或排序后在权值序列中二分，都是加速的好方法。
不用每次重建图，边权判断一下即可。
C o d e : \mathbf{Code:} Code:
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #pragma GCC optimize(2) #pragma GCC optimize(3) #define Rep(i, a, b) for (int i = (a); i <= (b); ++i) const int N = 1e6 + 10; const long long inf = 1e18; using namespace std; int n, m, K; long long dis[N]; queue <int> q; struct Graph { int to[N << 1], net[N << 1], w[N << 1], fl[N], len; inline void inc(int x, int y, int z) { return to[++len]=y,w[len]=z,net[len]=fl[x],fl[x]=len,void(); } inline void clear() { Rep(i, 1, len) to[i] = net[i] = w[i] = 0; Rep(i, 1, n) fl[i] = 0; len = 0; } inline void Inc(int x, int y, int z) { return inc(x, y, z), inc(y, x, z); } } G; struct Edge { int x, y, z; } e[N]; inline int read() {int s=0;char c=getchar();for(;!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-48;return s;} template <class T> inline void write(T x) { (x < 0 ? x = ~x + 1, putchar('-') : 0), (x > 9 ? write(x / 10) : void()); return putchar(x % 10 + 48), void(); } inline void Bfs(int st, int mid) { while (q.size()) q.pop(); Rep(i, 1, n) dis[i] = inf; dis[st] = 0, q.push(st); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = G.fl[u], v; v = G.to[i], i; i = G.net[i]) { int w = G.w[i] <= mid ? 0 : 1; if (dis[v] <= dis[u] + w) continue; dis[v] = dis[u] + w, (dis[v] <= K ? q.push(v) : void()); } } } inline bool check(int x) { Bfs(1, x); return dis[n] <= K; } int main(void) { n = read(), m = read(), K = read(); int maxn = 0; Rep(i, 1, m) { int x = read(), y = read(), z = read(); G.Inc(x, y, z), maxn = max(maxn, z); } int l = 0, r = maxn, mid; while (l + 1 < r) mid = (l + r) >> 1, (check(mid) ? r = mid : l = mid); m = (check(l) ? l : r), write(m >= maxn ? -1 : m); return 0; }