洛谷 P1119 灾后重建

洛谷 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 }

 

原文链接:https://www.cnblogs.com/SSummerZzz/p/11418149.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有