P1119 灾后重建(离线Floyed)

https://www.luogu.org/problem/show?pid=1119#sub
弗洛伊德其实是一个三维的dp
以k为中间点时，f[k][i][j]=min(f[k][i][j],f[k-1][i][j]);
这个题询问的时间是有顺序的，所以可以改为两维，
floyd算法中枚举的k是中转点，在这道题中就可以按时间顺序把点当作中转点，挨个儿加入图中，并且同时将‘时间恰当的询问’求出来（是指询问的时间

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> 
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,m,Q,t[209],w[209][209],dis[209][209],maxn;
struct H{
    int s,e,ti;
}q[50009];
int Floyed()
{
    int now=1;
    for(int k=0;k<n;k++)
    {   
        while(now<=Q&&t[k]>q[now].ti)//t[k]>q[now].ti
        {
            int qt=q[now].ti,qs=q[now].s,qe=q[now].e;
            if(t[qe]>=t[k]||t[qs]>=t[k]) printf("-1
");
            else
            {
                if(dis[qs][qe]!=maxn) printf("%d
",dis[qs][qe]);
                else printf("-1
");
            }           
            now++;
        }
        for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
              dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    while(now<=Q)
    {
        int qt=q[now].ti,qs=q[now].s,qe=q[now].e;
        if(dis[qs][qe]!=maxn) printf("%d
",dis[qs][qe]);
        else printf("-1
");
        now++;
    }
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    maxn=dis[n][n];
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&t[i]);
    }
    t[n]=t[n-1]+1;
    for(int i=1;i<=m;i++)
    {
        int x,y,l;
        scanf("%d%d%d",&x,&y,&l);
        dis[x][y]=l;
        dis[y][x]=l;
    }
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&q[i].s,&q[i].e,&q[i].ti);
    }
    Floyed();
    return 0;

}