题目地址：
https://www.luogu.com.cn/problem/P1119
题目背景：
B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。
题目描述：
给出B地区的村庄数
N
N
N
，村庄编号从
0
0
0
到
N
−
1
N-1
N
−
1
，和所有
M
M
M
条公路的长度，公路是双向的。并给出第
i
i
i
个村庄重建完成的时间
t
i
t_i
t
i
，你可以认为是同时开始重建并在第
t
i
t_i
t
i
天重建完成，并且在当天即可通车。若
t
i
t_i
t
i
为
0
0
0
则说明地震未对此地区造成损坏，一开始就可以通车。之后有
Q
Q
Q
个询问
(
x
,
y
,
t
)
(x,y,t)
(
x
,
y
,
t
)
，对于每个询问你要回答在第
t
t
t
天，从村庄
x
x
x
到村庄
y
y
y
的最短路径长度为多少。如果无法找到从
x
x
x
村庄到
y
y
y
村庄的路径，经过若干个已重建完成的村庄，或者村庄
x
x
x
或村庄
y
y
y
在第
t
t
t
天仍未重建完成，则需要输出
−
1
-1
−
1
。
输入格式：
第一行包含两个正整数
N
,
M
N,M
N
,
M
，表示了村庄的数目与公路的数量。
第二行包含
N
N
N
个非负整数
t
0
,
t
1
,
⋯
,
t
N
−
1
t_0,t_1,\cdots,t_{N-1}
t
0
,
t
1
,
⋯
,
t
N
−
1
，表示了每个村庄重建完成的时间，数据保证了
t
0
≤
t
1
≤
⋯
≤
t
N
−
1
t_0\le t_1\le \cdots \le t_{N-1}
t
0
≤
t
1
≤
⋯
≤
t
N
−
1
。
接下来
M
M
M
行，每行
3
3
3
个非负整数
i
,
j
,
w
i,j,w
i
,
j
,
w
，
w
w
w
为不超过
10000
10000
10000
的正整数，表示了有一条连接村庄
i
i
i
与村庄
j
j
j
的道路，长度为
w
w
w
，保证
i
≠
j
i\neq j
i
=
j
，且对于任意一对村庄只会存在一条道路。
接下来一行也就是
M
+
3
M+3
M
+
3
行包含一个正整数
Q
Q
Q
，表示
Q
Q
Q
个询问。
接下来
Q
Q
Q
行，每行
3
3
3
个非负整数
x
,
y
,
t
x,y,t
x
,
y
,
t
，询问在第
t
t
t
天，从村庄
x
x
x
到村庄
y
y
y
的最短路径长度为多少，数据保证了
t
t
t
是不下降的。
输出格式：
共
Q
Q
Q
行，对每一个询问
(
x
,
y
,
t
)
(x,y,t)
(
x
,
y
,
t
)
输出对应的答案，即在第
t
t
t
天，从村庄
x
x
x
到村庄
y
y
y
的最短路径长度为多少。如果在第
t
t
t
天无法找到从
x
x
x
村庄到
y
y
y
村庄的路径，经过若干个已重建完成的村庄，或者村庄
x
x
x
或村庄
y
y
y
在第
t
t
t
天仍未修复完成，则输出
−
1
-1
−
1
。
数据范围：
对于
30
30%
30
的数据，有
N
≤
50
N\le50
N
≤
50
；
对于
30
30%
30
的数据，有
t
i
=
0
t_i=0
t
i
=
0
，其中有
20
20%
20
的数据有
t
i
=
0
t_i=0
t
i
=
0
且
N
>
50
N>50
N
>
50
；
对于
50
50%
50
的数据，有
Q
≤
100
Q\le100
Q
≤
100
；
对于
100
100%
100
的数据，有
1
≤
N
≤
200
1\le N\le200
1
≤
N
≤
200
，
0
≤
M
≤
N
×
(
N
−
1
)
2
0\le M\le\dfrac{N\times(N-1)}{2}
0
≤
M
≤
2
N
×
(
N
−
1
)
，
1
≤
Q
≤
50000
1\le Q\le50000
1
≤
Q
≤
50000
，所有输入数据涉及整数均不超过
1
0
5
10^5
1
0
5
。
回忆一下Floyd算法
https://blog.csdn.net/qq_46105170/article/details/113821689
，其可以算出只经过村庄
0
∼
k
0\sim k
0
∼
k
中转的所有点对的最短路（“中转”的意思是不包括起点和终点）。那么我们要回答询问，只需要先求出询问的时间的那一刻，哪些村庄已经建好，然后按Floyd算法一路递推到最后修好的村庄即可。由于题目里的村庄是按编号修好的，询问的时间也是递增的，所以可以按
0
,
1
,
.
.
.
0,1,…
0
,
1
,
…
的顺序递推。代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m;
int tm[N];
int g[N][N];
void update(int cur_city) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = min(g[i][j], g[i][cur_city] + g[cur_city][j]);
}
int main() {
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &tm[i]);
g[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
g[a][b] = g[b][a] = min(g[a][b], w);
}
int Q;
scanf("%d", &Q);
int cur_city = 0;
while (Q--) {
int a, b, t;
scanf("%d%d%d", &a, &b, &t);
while (tm[cur_city] <= t && cur_city < n) update(cur_city++);
// 这里需要额外判断一下起点和终点有没有修好
printf("%d\n",
a < cur_city && b < cur_city && g[a][b] < INF ? g[a][b] : -1);
}
}
总时间复杂度
O
(
n
3
)
O(n^3)
O
(
n
3
)
，空间
O
(
n
2
)
O(n^2)
O
(
n
2
)
。