题解 洛谷P1119 【灾后重建】

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

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

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

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

#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
");//村庄x尚未建成,村庄x尚未建成或村庄x与村庄y在t时并不连通
		} else {
			printf("%d
", edge[x][y]);
		}
	}
}

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