P1119 灾后重建 floyd c++

1. 此题的无穷大不能按题目给的不超过10000，不然会WA五个测试点，所以inf可以赋值为0x3f3f3f3f或者100000，即可通过；
   
2. 而且每次询问的时候，可以发现每个村庄的修建时间是递增的，所以我们可以每次加一个可用村庄，也就是多一个中转点的选择，去更新整个邻接矩阵；
3. 这个题目更深一层地了解Floyd算法，参考洛谷的题解：
   

#include 
using namespace std;
int n, m;
int t[210];//每个村建设所需时间
int d[210][210];//邻接矩阵
int inf = 0x3f3f3f3f;
void floyd(int k) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		}
	}
}
void init() {
	//每个村庄维修所要的时间
	for (int i = 0; i < n; i++)
		cin >> t[i];
	//初始化邻接矩阵
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				d[i][j] = 0;
			else
				d[i][j] = inf;
		}
	}

	for (int i = 0; i < m; i++) {
		int x, y, val;
		cin >> x >> y >> val;
		d[x][y] = d[y][x] = val; //此题为无向图
	}
}
int main() {
	cin >> n >> m;
	init();
	int q;
	int now = 0;//当前几个村已建成
	cin >> q;
	while (q--) {
		int x, y, temp;
		cin >> x >> y >> temp;
		while (t[now] <= temp && now < n) {
			floyd(now);///依次更新中转点，使它可以被用来更新其他的点
			now++;
		}
		//某个村还未建成，不能省略这个条件判断，不然邻接矩阵有的值不为inf，会误以为可以到达，但这个村还没建成
		if (t[x] > temp || t[y] > temp)
			cout << -1 << endl;
		else {
			if (d[x][y] == inf)
				cout << -1 << endl;
			else
				cout << d[x][y] << endl;
		}
	}
	return 0;
}