题目背景

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

题目描述

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

输入输出格式

输入格式：

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

第二行包含N个非负整数t0,t1,…,tN−1​，表示了每个村庄重建完成的时间，数据保证了t0≤t1≤…≤tN−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%的数据，有ti=0，其中有20%20%的数据有ti=0且N>50；

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

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

说明

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

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

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

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

#代码

cpp
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;
}