【題意】：給出一個無向圖，Harry Potter的目的是從1走到n，而Voldemort為了阻止他，使用魔法毀掉了圖中的一條邊，問最壞情況下Harry要走的最短路是多少。

【題解】：先考慮這么一個問題，如果不允許毀掉圖中的邊，那么求一次最短路即可。回到初始問題，這是一個最小值最大化的問題，顯然最壞情況下肯定是刪掉最短路上的一條邊，這個很容易理解吧。具體做法：先求一次最短路并記錄最短路徑，枚舉刪掉最短路上的每一條邊，再求最短路，這些結果中最大值就是最后答案；如果某次刪邊使得1無法到達n，那么可以跳出枚舉，因為這已經是最壞的情況。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 using namespace std;
 6 #define maxn 1005
 7 #define maxm 100500
 8 const int inf = 1 << 30;
 9 int n, m, s, x;
10 int eh[maxn], dist[maxn], pre[maxn], p[maxn], tot;
11 bool visit[maxn], flag;
12 struct Edge {
13     int u, v, w, next;
14 }et[maxm];
15 
16 void init() {
17     tot = 0;
18     memset(eh, -1, sizeof(eh));
19 }
20 
21 void addedge(int u, int v, int w) {
22     Edge e = {u, v, w, eh[u]};
23     et[tot] = e;
24     eh[u] = tot++;
25 }
26 
27 int spfa() {
28     queue<int> que;
29     fill(dist, dist + maxn, inf);
30     memset(visit, false, sizeof(visit));
31     dist[s] = 0, visit[s] = true;
32     que.push(s);
33     while(!que.empty()) {
34         int u = que.front();
35         que.pop();
36         visit[u] = false;
37         for(int i = eh[u]; i != -1; i = et[i].next) {
38             int v = et[i].v, w = et[i].w;
39             if(dist[u] + w < dist[v] && i != x) {
40                 dist[v] = dist[u] + w;
41                 if(x == -1) pre[v] = i, p[v] = u;
42                 if(!visit[v]) {
43                     que.push(v);
44                     visit[v] = true;
45                 }
46             }
47         }
48     }
49     return dist[n];
50 }
51 
52 int solve() {
53     x = -1;
54     int ans = spfa();
55     if(ans == inf) return -1;
56     for(int i = n; i != s; i = p[i]) {
57         x = pre[i];
58         ans = max(ans, spfa());
59         if(ans == inf) return -1;
60     }
61     return ans;
62 }
63 
64 int main() {
65     int T;
66     scanf("%d", &T);
67     while(T--) {
68         scanf("%d%d", &n, &m);
69         init();
70         s = 1;
71         for(int i = 0; i < m; i++) {
72             int u, v, w;
73             scanf("%d%d%d", &u, &v, &w);
74             addedge(u, v, w);
75             addedge(v, u, w);
76         }
77         int ans = solve();
78         printf("%d\n", ans);
79     }
80     return 0;
81 }