题目链接：

---

 

暴力的做法很容易想到，对于每次询问，将修好的点加到图上，复杂度可以是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 
      
        2 #include 
       
         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\n");27             else printf("%d\n", 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 }