给定一个无向图，求删掉一条边之后的最短路，但是删的是哪条边你不知道，问最坏情况下最短路是多长（）

分析：

综合上述讨论，本题的做法就是，先求一次最短路，用pre数组记录【其中一条】最短路径，然后遍历这条最短路径上的边，删除后各求一次路径，取他们中从起点到终点的最短距离的最大值即可

  1 //// patest.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
  2 ////
  3 #include "pch.h"
  4 
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <cstdlib>
  8 #include <cstring>
  9 #include <iostream>
 10 #include <iterator>
 11 #include <algorithm>
 12 #include <string>
 13 #include <set>
 14 #include <unordered_set>
 15 #include <map>
 16 #include <unordered_map>
 17 #include <vector>
 18 #include <stack>
 19 #include <queue>
 20 #include <deque>
 21 
 22 using namespace std;
 23 const int INF = 0x7fffffff;
 24 const int maxn = 1010;
 25 const int maxk = 10010;
 26 
 27 //void printVector(vector<int>& vt) {
 28 //    int size = vt.size();
 29 //    for (int i = 0; i < size; i++) {
 30 //        printf("%d", vt[i]);
 31 //        if (i != size - 1) printf(" ");
 32 //    }
 33 //    printf("
");
 34 //
 35 //}
 36 
 37 
 38 int n, m, st, ed;
 39 bool vis[maxn];
 40 int d[maxn];
 41 int G[maxn][maxn];
 42 
 43 vector<int> pre[maxn];
 44 
 45 void Dijkstra(int s) {
 46 
 47     memset(vis, false, sizeof(vis));
 48     fill(d, d + maxn, INF);
 49     d[s] = 0;
 50     for (int i = 0; i < n; i++) {
 51         int u = -1, MIN = INF;
 52         for (int j = 1; j <= n; j++) {
 53             if (vis[j] == false && d[j] < MIN) {
 54                 MIN = d[j];
 55                 u = j;
 56             }
 57         }
 58 
 59         if (u == -1) return;
 60         vis[u] = true;
 61         for (int v = 1; v <= n; v++) {
 62             if (vis[v] == false && G[u][v] != INF) {
 63                 if (d[u] + G[u][v] < d[v]) {
 64                     d[v] = d[u] + G[u][v];
 65                     pre[v].clear();
 66                     pre[v].push_back(u);
 67                 }
 68                 else if (d[u] + G[u][v] == d[v]) {
 69                     pre[v].push_back(u);
 70                 }
 71             }
 72         }
 73         
 74     }
 75 }
 76 
 77 vector<pair<int, int>> ans;
 78 
 79 void DFS(int index) {
 80     for (auto next : pre[index]) {
 81         ans.push_back(make_pair(index, next));
 82         DFS(next);
 83     }
 84 }
 85 
 86 int maxTime = -1;
 87 int main() {
 88 
 89     fill(G[0], G[0] + maxn * maxn, INF);
 90 
 91     scanf("%d%d", &n, &m);
 92     st = 1, ed = n;
 93     for (int i = 0; i < m; i++) {
 94         int u, v, time;
 95         scanf("%d%d%d", &u, &v, &time);
 96         G[u][v] = G[v][u] = time;
 97     
 98     }
 99 
100     Dijkstra(st);
101     DFS(ed);
102 
103     int lastTime;
104     for (int i = 0; i < ans.size(); i++) {
105         int u = ans[i].first;
106         int v = ans[i].second;
107         if (i > 0) {
108             int id1 = ans[i - 1].first;
109             int id2 = ans[i - 1].second;
110             G[id1][id2] = G[id2][id1] = lastTime;
111         }
112 
113         lastTime = G[u][v];
114         G[u][v] = G[v][u] = INF;
115 
116         Dijkstra(st);
117         maxTime = max(maxTime, d[ed]);
118 
119     }
120 
121     if (maxTime == INF) printf("It's a bug!!!
");
122     else printf("%d
", maxTime);
123     
124     
125     
126 
127     return 0;
128 }