题目链接：https://www.luogu.org/problemnew/show/P1119
暴力的做法很容易想到，对于每次询问，将修好的点加到图上，复杂度可以是O(mlogn*q)，粗略算一下会炸。看到N<=200，忽然想到了Floyd，又想将询问保存，倒序处理，也就是每次删边，毫无疑问这是错误的。然后翻看dalao的博客，才意识到，原来Floyd是这样的！Floyd的原理是动态规划，d[i][j]=min(d[i][j],d[i][k]+dp[k][j])，关键是在此之前要得到d[i][k]和d[k][j]，因此是先枚举k。在枚举到k之前，k并不会作为某条最短路的中间点。所以只要保证每个结点是依次加入到图中的，那么每次用新加入的结点作为中间点更新所有的最短路，得到的就是此时图上的最短路。这道题的输入刚好是按加入顺序（每次询问t递增）。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 205, inf = 0x3f3f3f3f; 5 6 int repair[maxn], dist[maxn][maxn]; 7 8 int main() { 9 int n, m, q; 10 scanf("%d%d", &n, &m); 11 for (int i = 0; i < n; ++i) scanf("%d", &repair[i]); 12 repair[n] = inf; 13 memset(dist, inf, sizeof(dist)); 14 for (int i = 1; i <= m; ++i) { 15 int u, v, w; 16 scanf("%d%d%d", &u, &v, &w); 17 dist[u][v] = dist[v][u] = w; 18 } 19 scanf("%d", &q); 20 int x, y, t; 21 scanf("%d%d%d", &x, &y, &t); 22 --q; 23 for (int k = 0; k <= n; ++k) { 24 while (t < repair[k]) { 25 if (repair[x] > t || repair[y] > t || dist[x][y] == inf) 26 printf("-1 "); 27 else printf("%d ", dist[x][y]); 28 if (!q) return 0; 29 scanf("%d%d%d", &x, &y, &t); 30 --q; 31 } 32 for (int i = 0; i < n; ++i) 33 for (int j = 0; j < n; ++j) 34 if (dist[i][j] > dist[i][k] + dist[k][j]) 35 dist[i][j] = dist[i][k] + dist[k][j]; 36 } 37 return 0; 38 }