洛谷题解P1119【灾后重建】

题目背景

$B$地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。

题目描述

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

输入输出格式

输入格式:

第一行包含两个正整数$N,M$,表示了村庄的数目与公路的数量。

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

接下来$M$行,每行$3$个非负整数$i, j, w$,$w$为不超过$10000$的正整数,表示了有一条连接村庄$i$与村庄$j$的道路,长度为$w$,保证$i≠j$,且对于任意一对村庄只会存在一条道路。

接下来一行也就是$M+3$行包含一个正整数$Q$,表示$Q$个询问。

接下来$Q$行,每行$3$个非负整数$x, y, t$,询问在第$t$天,从村庄$x$到村庄$y$的最短路径长度为多少,数据保证了$t$是不下降的。

输出格式:

共$Q$行,对每一个询问$(x, y, t)$输出对应的答案,即在第$t$天,从村庄$x$到村庄$y$的最短路径长度为多少。如果在第$t$天无法找到从$x$村庄到$y$村庄的路径,经过若干个已重建完成的村庄,或者村庄$x$或村庄$y$在第$t$天仍未修复完成,则输出$-1$。

输入输出样例

输入样例#1:

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

输出样例#1:

-1
-1
5
4

说明

对于$30\%$的数据,有$N≤50$;

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

对于$50\%$的数据,有$Q≤100$;

对于$100\%$的数据,有$N≤200$,$M≤N \times (N-1)/2$,$Q≤50000$,所有输入数据涉及整数均不超过$100000$。

说明

本题基本上是Floyd的模版题,适合初学Floyd的OIer练习。

本题的重点在于并非在每一个时刻,每一个节点都可以到达,所以应枚举目前所有可以到达的节点k,并以k为中转点进行更新。

同时,因为出题人已经给数据排好了顺序,发现未建成时直接中断即可。

闲话少说,主要看代码注释。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio> 
#include<algorithm>
using namespace std;

const int MAXN = 200 + 5;
const int INF = 1e9;

int edge[MAXN][MAXN], times[MAXN];
int n, m, q;

/*
init()函数:
Floyd初始化
*/
void init() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
edge[i][j] = (i == j ? 0 : INF);//节点到自身的距离为0
}
}
}

/*
addEdge()函数:
在邻接矩阵中添加一条(双向)边
*/
void addEdge(int i, int j, int v) {
edge[i][j] = edge[j][i] = v;//双向边处理
}

/*
input()函数:
输入数据
*/
void input() {
scanf("%d%d", &n, &m);
init(); //读入n, m后进行初始化
for(int i = 0; i < n; i++) {
scanf("%d", &times[i]);
}
for(int i = 0; i < m; i++) {
int x, y, v;

scanf("%d%d%d", &x, &y, &v);
addEdge(x, y, v);
}
}

/*
update()函数:
以k为中转点更新最短路
*/
void update(int k) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
}
}
}

void work() {
int cur = 0;

scanf("%d", &q);
for(int i = 0; i < q; i++) {
int x, y, t;

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

//这里是重点
while(times[cur] <= t && cur < n) {
update(cur);//若当前可以经过村庄cur,以cur为中转点更新最短路径
cur++;
}
if(times[x] > t || times[y] > t || edge[x][y] == INF) {
printf("-1\n");//村庄x尚未建成,村庄x尚未建成或村庄x与村庄y在t时并不连通
} else {
printf("%d\n", edge[x][y]);
}
}
}

int main() { //简洁的main()函数
input();
work();

return 0;
}

文章作者: Helium
文章链接: https://keepthethink.github.io/archives/1827780785/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Heliumの博客