洛谷P1119灾后重建——Floyd

题目：https://www.luogu.org/problemnew/show/P1119

N很小，考虑用Floyd；

因为t已经排好序，所以逐个加点，Floyd更新即可；

这也给我们一个启发，如果t不是排好序的，也可以离线处理，排序再做。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,q,f[205][205],t[205],nw;
int main()
{
    memset(f,0x3f,sizeof f);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",&t[i]),f[i][i]=0;//
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        f[x][y]=f[y][x]=z;//
    }
    scanf("%d",&q);
    int x,y,tim;
    while(q--)
    {
        scanf("%d%d%d",&x,&y,&tim);
        while(nw<n&&t[nw]<=tim)
        {
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    f[j][k]=min(f[j][k],f[j][nw]+f[nw][k]);
            nw++;
        }
        if(f[x][y]==0x3f3f3f3f||t[x]>tim||t[y]>tim)printf("-1
");//
        else printf("%d
",f[x][y]);
    }
    return 0;
}