洛谷 P1119 灾后重建

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

借用大佬的一句话：floyd的算法本质，

从i城市到j城市，通过前k个城市的贪心后得到的距离矩阵，即得到的距离矩阵是通过前k个城市（的贪心）之后的最短路。

那么这题就变得简单了。

---

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <stack>
 7 #include <set>
 8 #include <cmath>
 9 #include <string>
10 #include <map>
11 #include <cmath>
12 #include <iomanip>
13 using namespace std;
14  
15 typedef long long ll;
16 #define inf 1e8
17 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
18 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
19 #define per(i,j,k) for(int i = (j); i >= (k); i--)
20 #define per__(i,j,k) for(int i = (j); i > (k); i--)
21 
22 const int n = (int)2e2 + 10;
23 int f[n][n];
24 int tim[n];
25 
26 int main(){ 
27 
28     int n,m;
29     scanf("%d%d",&n,&m);
30 
31     rep__(i,0,n) scanf("%d",tim + i);
32     rep__(i,0,n) rep__(j,0,n){
33         if(i == j) f[i][j] = 0;
34         else f[i][j] = inf;
35     }
36     int u,v,w,t;
37     rep__(i,0,m){
38         scanf("%d%d%d",&u,&v,&w);
39         f[u][v] = f[v][u] = w;
40     }
41     int q;
42     scanf("%d",&q);
43     int k = 0;
44     while(q--){
45         scanf("%d%d%d",&u,&v,&t);
46         while(k < n && tim[k] <= t){
47             rep(i,0,n - 1) rep(j,0,n - 1){
48                 f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
49             }
50             k++;
51         }
52 
53         if(f[u][v] == inf  || tim[u] > t || tim[v] > t) printf("-1\n");
54         else printf("%d\n",f[u][v]);
55     }
56 
57     getchar(); getchar();
58     return 0;
59 }