洛谷 P1119 灾后重建（Floyd）

嗯...

题目链接：https://www.luogu.org/problem/P1119

这道题是一个Floyd的很好的题目，在Floyd的基础上加一点优化：

中转点k在这里不能暴力枚举，否则会超时，我们则可以用时间的限制来优化一下，用一个while，只有中转站被修复（即中转站修复时间小于t）时，k才能作为中转站，也就是指枚举在t时，被修复了的中转站，这样时间复杂度会降低一些...

本题细节问题：

1.每个村庄的下标是从0开始的

2.因为memset比较神奇，所以最后判-1时，要找一个比0x3f的数大的数进行判断，并且是>=

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 int g[][], a[], n, m;

 inline void update(int k){

     for(int i = ; i < n; i++){

         for(int j = ; j < n; j++){

             g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

         }

     }

     return;

 }

 int main(){

     memset(g, 0x3f, sizeof(g));

     scanf("%d%d", &n, &m);

     for(int i = ; i < n; i++) {scanf("%d", &a[i]); g[i][i] = ;}//枚举细节

     for(int i = ; i <= m; i++) {

         int x, y, z;

         scanf("%d%d%d", &x, &y, &z);

         g[x][y] = g[y][x] = z;

     }

     int q, now = ;

     scanf("%d", &q);

     for(int i = ; i <= q; i++) {

         int u, v, t;

         scanf("%d%d%d", &u, &v, &t);

         while(a[now] <= t && now < n){

             update(now);

             now++;

         }

         if(g[u][v] >= 0x3f3f3f3f || a[u] > t || a[v] > t) printf("-1\n");

         else printf("%d\n", g[u][v]);

     }

     return ;

 }

AC代码