P1119 灾后重建

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int INF = 0x3f3f3f3f;

int n, m;
int t[MAXN];                 // 各村庄的重建完成时间
int dista[MAXN][MAXN];       // 最短路矩阵

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dista[i][j] = (i == j ? 0 : INF);
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        dista[a][b] = dista[b][a] = min(dista[a][b], w);
    }

    int q;
    cin >> q;

    int k = -1;                // 已经当作「中间点」用过的最大村庄编号
    while (q--) {
        int x, y, day;
        cin >> x >> y >> day;

        // 起点或终点当天还没修好，直接无解
        if (t[x] > day || t[y] > day) {
            cout << -1 << "\n";
            continue;
        }

        // 把重建时间不超过 day 的村庄加入「中间点」集合
        while (k + 1 < n && t[k + 1] <= day) {
            k++;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dista[i][j] = min(dista[i][j], dista[i][k] + dista[k][j]);
                }
            }
        }

        int ans = dista[x][y];
        cout << (ans >= INF ? -1 : ans) << "\n";
    }

    return 0;
}