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都采用了将第一层循环灵活运用的方法。

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