P1119 灾后重建

传送门

Folyd

本题需要对Folyd有较深的理解

考虑Folyd的思想

枚举每个中转点

用这些点去尝试更新其它所有两点的距离

如果有点不能走，显然它不能作为中转点

本题在不同的时间有不同的点能走

用Floyd可以枚举所有可以走的中转点，更新其它两点的距离

好像复杂度是 O(n^3 * q)

但是

一个点好了以后就一直能走

所以一个点更新过其它点后就不再需要用它重复更新其它点了

而且每个点的恢复时间是递增的，询问的时间也是递增的

那就很方便搞了

复杂度 O(n^3)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=207,INF=0x3f3f3f3f;
int n,m,q;
int t[N];
int mp[N][N];
int main()
{
    memset(mp,INF,sizeof(mp));
    int a,b,c;
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%d",&t[i]); t[n]=23333333;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        mp[a][b]=mp[b][a]=c;
    }
    cin>>q;
    int pos=0;//记录上一波更新到了哪里
    while(q--)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(t[a]>c||t[b]>c)//如果本身都没好就肯定走不通
        {
            printf("-1
");
            continue;
        }
        for(;t[pos]<=c;pos++)//用当前所有新恢复的点更新其它所有两点间的距离
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(mp[i][pos]+mp[pos][j]<mp[i][j]) mp[i][j]=mp[i][pos]+mp[pos][j];
        printf("%d
",mp[a][b]==INF ? -1 : mp[a][b]);
    }
    return 0;
}