灾后重建（洛谷P1119，图论floyd）

P1119 灾后重建

题目背景

题目描述

给出 $BBB地区的村庄数NNN，村庄编号从000到N−1N-1N−1，和所有MMM条公路的长度，公路是双向的。并给出第iii个村庄重建完成的时间tit_iti，你可以认为是同时开始重建并在第tit_iti天重建完成，并且在当天即可通车。若tit_iti为000则说明地震未对此地区造成损坏，一开始就可以通车。之后有QQQ个询问(x,y,t)(x, y, t)(x,y,t)，对于每个询问你要回答在第ttt天，从村庄xxx到村庄y的最短路径长度为多少。如果无法找到从xxx村庄到yyy村庄的路径，经过若干个已重建完成的村庄，或者村庄xxx或村庄yyy在第t天仍未重建完成，则需要返回−1-1−1。$

输入格式

第一行包含两个正整数

第二行包含 $NNN个非负整数t0,t1,…,tN−1t_0, t_1,…, t_{N-1}t0,t1,…,tN−1，表示了每个村庄重建完成的时间，数据保证了t0≤t1≤…≤tN−1t_0 ≤ t_1 ≤ … ≤ t_{N-1}t0≤t1≤…≤tN−1。$

接下来

接下来一行也就是

接下来

输出格式

共

输入输出样例

输入 #1

输出 #1

-1
-1
5
4

说明/提示

对于 $30%30\%30%的数据，有N≤50；$

对于 $30%30\%30%的数据，有ti=0t_i= 0ti=0，其中有20%20\%20%的数据有ti=0且N>50；$

对于 $50%50\%50%的数据，有Q≤100；$

对于 $100%100\%100%的数据，有N≤200，M≤N×(N−1)/2，Q<=50000,所有输入数据涉及整数均不超过100000100000100000。$

1 for(int k=1;k<=n;k++){
2     for(int i=1;i<=n;i++){
3         for(int j=1;j<=n;j++){
4             f[i][j]=f[i][k]+f[k][j];
5         }
6     }
7 }

 1 #include<cstdio>
 2 const int maxn=200+10,inf=0x3f3f3f3f;
 3 int a[maxn],w[maxn][maxn],f[maxn][maxn];
 4 int n;
 5 void Init(){
 6     for(int i=0;i<n;i++){
 7         for(int j=0;j<n;j++){
 8             f[i][j]=inf;
 9         }
10     }
11     for(int i=0;i<n;i++) f[i][i]=0;
12 }
13 void work(int k){
14     for(int i=0;i<n;i++){
15         for(int j=0;j<n;j++){
16             if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];
17         }
18     }
19 }
20 int main(){
21     int m;
22     scanf("%d%d",&n,&m);
23     for(int i=0;i<n;i++) scanf("%d",&a[i]);//读入每个村庄修建好时间（因为按顺序给出，所以不用先记录在排序）
24     Init();//初始化（普通的floyd）
25     for(int i=1;i<=m;i++){
26         int x,y,z;
27         scanf("%d%d%d",&x,&y,&z);
28         f[x][y]=f[y][x]=z;//初始化（普通的floyd）
29     }
30     int q;
31     scanf("%d",&q);
32     int last=0;
33     for(int i=1;i<=q;i++){
34         int x,y,t;
35         scanf("%d%d%d",&x,&y,&t);//读入每个询问
36         if(a[x]>t||a[y]>t){
37             printf("-1
");
38             continue;
39         }//如果x或y未修建好，直接输出-1
40         int j;
41         for(j=last;j<n;j++){
42             if(a[j]>t) break;
43             work(j);
44         }//寻找在t之前修好的且没有用过他来松弛的村庄来松弛，结合之前的初始化，开始时给f数组附上了一些值，不用担心这会影响结果，因为x，y在t或t之前被修好的
45         last=j;//所以j更新t以后的对答案无太大影响，且刚好他更新完了后边的，这就是floyd算法，所以之前的x或y是否修建好的判断一定要有，不然若j更新了，答案会错
46         if(f[x][y]==inf) printf("-1
");
47         else printf("%d
",f[x][y]);
48     }
49     return 0;
50 }

View Code