Luogu 1119(Floyd方程理解)

1119 灾后重建
解:对于 Floyd 的方程式$dp(k, i, j)$是只有前$k$个点中$i$到$j$的最短路径,对于转移, 路径$(i,j)$有过$k$点或者不过$k$两种状态。然后滚动数组得到普遍的那个方程。
对于这题因为$t_i$单调递增,并且询问$t$也单调递增,所以每次相当于加入一些点。Floyd 的方程就能完成这一点。每次更新到只有前$k$个点即可,这$k$个点都是重建完的。答案就是$ma_{ij}$,并且起点终点重建完了。

知识点: Floyd 的方程式$dp(k, i, j)$是只有前$k$个点中$i$到$j$的最短路径
此题与CF 1037D都采用了将第一层循环灵活运用的方法。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 200 + 5, INF = 1000000000;
int n, m, ti[MAXN], ma[MAXN][MAXN], Q;
void floyd(int k) {
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
if (i != j && i != k && k != j) ma[i][j] = std::min(ma[i][j], ma[i][k] + ma[k][j]);
}
void clean() {
for (int i = 0; i <= n + 1; i++) ti[i] = INF;
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++) ma[i][j] = INF;
}
int solve() {
clean();
for (int i = 0; i < n; i++) scanf("%d", &ti[i]);
for (int x, y, w, i = 1; i <= m; i++) scanf("%d%d%d", &x, &y, &w), ma[x][y] = ma[y][x] = w;
scanf("%d", &Q);
int now = 0;
while (Q--) {
int x, y, t; scanf("%d%d%d", &x, &y, &t);
while (ti[now] <= t) {
floyd(now), now++;
}
//printf("now = %d, ma[x][y] = %d\n", now, ma[x][y]);
if (ti[x] > t || ti[y] > t || ma[x][y] == INF) {printf("-1\n"); continue; }
printf("%d\n", ma[x][y]);
}
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------