AC日记——灾后重建 洛谷 P1119

灾后重建

思路：

　　看到n<=200，思考弗洛伊德算法；

　　如何floyed呢？

　　floyed是一种动态规划求最短路的算法；

　　它通过枚举中间点来更新两点之间最短路；

　　回到这个题本身；

　　所有点的重建完成的时间和询问的时间都已经排好序了；

　　所以，我们把floyed拆开；

　　对于一个三维的k，i，j的floyed算法；

　　我们判断当前的询问在哪两个相邻的k之间；

　　然后，我们判断当时的连通性以及最短路情况；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define INF 0x7ffffff

int n,m,f[][][],ti[];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

int main()

{

    in(n),in(m);

    for(int k=;k<=n+;k++)

    {

        for(int i=;i<n;i++)

        {

            for(int j=;j<n;j++) f[k][i][j]=INF;

        }

    }

    for(int i=;i<n;i++) in(ti[i]);

    int u,v,w;

    for(int i=;i<=m;i++)

    {

        in(u),in(v),in(w);

        f[][u][v]=w;

        f[][v][u]=w;

    }

    for(int k=;k<=n;k++)

    {

        for(int i=;i<n;i++)

        {

            for(int j=;j<n;j++)

            {

                f[k][i][j]=min(f[k-][i][j],f[k-][i][k-]+f[k-][k-][j]);

            }

        }

    }

    in(m);int tot=;

    for(int i=;i<=m;i++)

    {

        in(u),in(v),in(w);

        if(ti[u]>w||ti[v]>w)

        {

            printf("-1\n");

            continue;

        }

        while(ti[tot]<=w&&tot<n) tot++;

        int now=tot-;

        if(ti[now]<=w)

        {

            if(f[tot][u][v]==INF) printf("-1\n");

            else printf("%d\n",f[tot][u][v]);

        }

        else printf("-1\n");

    }

    return ;

}