题解 P1119 【灾后重建】
智子
2019-06-01 10:07:22
本题基本上是Floyd的模版题，适合初学Floyd的OIer练习。
本题的重点在于并非在每一个时刻，每一个节点都可以到达，所以应枚举目前所有可以到达的节点k，并以k为中转点进行更新。
同时，因为出题人已经给数据排好了顺序，发现未建成时直接中断即可。
闲话少说，主要看代码注释。
```cpp
#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", ×[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;
}
```