[Luogu P1119]灾后重建

这是一道考Floyd本质的题。

回忆一下Floyd的原理，三层循环，最外层循环枚举的是中转点，也就是用两点到中转点距离之和来更新最短路。然后来看下题目，重建时间是按照从小到大排序的，也就是说，当第i个村庄刚重建完成时，前i个村庄全部重建完成，而后面的都没有重建完成。那么在枚举中转点的时候就可以在线操作，如果当前询问时间比已经更新过的中转点now的时间大，则now++继续更新直到时间为当前询问时间，输出答案即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define B cout << "Break" << endl;
#define A(x) cout << #x << "=" << x << endl;
#define inf 1e9
using namespace std;
#define N 210
int t[N],dis[N][N],n,m;
void reset()
{
    for(int i = 0;i <= N;i++)
    {
        dis[i][i] = 0;
        for(int j = 0;j <= N;j++)
        {
            if(i != j) dis[i][j] = inf;
        }
    }
    return;
}
void floyd(int k)
{
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            dis[j][i] = dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);//Floyd板子
        }
    }
    return;
}
int main()
{
    reset();
    scanf("%d %d",&n,&m);
    for(int i = 0;i < n;i++) scanf("%d",&t[i]);
    for(int i = 0;i < m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        dis[u][v] = dis[v][u] = w;
    }
    int cnt = 2;
    cin >> cnt;
    int now = 0;//用now记录当前枚举到的中转点
    while(cnt--)
    {
        int a,b,tt;
        scanf("%d %d %d",&a,&b,&tt);
        while(t[now] <= tt && now < n)//如果now对应的时间比询问时间少则继续枚举中转点
        {
            floyd(now);
            now++;
        }
        if(t[a] > tt || t[b] > tt || dis[a][b] == inf) printf("-1
");//如果当前询问时间小于起点和终点的重建时间或者不连通则无解。
        else printf("%d
",dis[a][b]);
    }
}