url: https://www.luogu.com.cn/problem/P1119

tag:
图论，枚举，最短路

思路：
这道题可以用floyd算法来做，每次询问，都将当前这个时间可以重建完的村庄用floyd算法更新一下所有点的最短路。最后判断一下这个询问的两个村庄是否重建完以及是否可以联通，如果重建完并且联通就输出最短路，否则输出-1

代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 220;
int n, m, q;
int f[N][N];
int a[N];

inline void update(int k)
{
    for (int i = 0; i < n; i ++)
        for (int j = 0;  j< n; j ++)
            f[i][j] = f[j][i] = min(f[i][j], f[i][k] + f[k][j]);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++) f[i][j] = 0x3f3f3f3f;
        f[i][i] = 0;
    }
    for (int i = 0; i < m; i ++)
    {
        int x, b, w;
        cin >> x >> b >> w;
        f[x][b] = f[b][x] = w;
    }
    cin >> q;
    int idx = 0;
    for (int i = 0; i < q; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        while (a[idx] <= z && idx < n)
        {
            update(idx);
            idx ++;
        }
        if (a[x] > z || a[y] > z) cout << -1 << endl;
        else if (f[x][y] == 0x3f3f3f3f) cout << -1 << endl;
        else cout << f[x][y] << endl;
    }
    return 0;
}