P1119 灾后重建

P1119 灾后重建

随着时间增加，图中的边数也增加，求每个时间的最短路。考虑每增加一条边，就将其在所有道路中更新答案，所以用 floyed 。

查看代码

#include <iostream>
#include <cstdio>
#include <climits>
#define INF INT_MAX
using namespace std;
const int N = 210, M = 4e4 + 10;
int n, t[N], dis[N][N];
int main ()
{
    int m, a, b, c;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = (i == j ? 0 : INF);
    for (int i = 0; i < n; i++)
        cin >> t[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        dis[a][b] = dis[b][a] = c;
    }
    cin >> m;
    int nt = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        while (t[nt] <= c && nt < n)
        {
            for (int l = 0; l < n; l++)
                for (int r = 0; r < n; r++)
                    if (dis[l][nt] != INF && dis[nt][r] != INF)
                    dis[l][r] = dis[r][l] = min(dis[l][r], dis[l][nt] + dis[nt][r]);
            nt++;
        }
        if (t[a] > c || t[b] > c || (dis[a][b] == INF))
            puts("-1");
        else
            cout << dis[a][b] << endl;
    }
    return 0;
}