【洛谷P1119题解】灾后重建——（floyd）

这道题告诉我，背的掉板子并不能解决一切问题，理解思想才是关键，比如不看题解，我确实想不清楚这题是弗洛伊德求最短路

（我不该自不量力的说我会弗洛伊德了我错了做人果然要谦虚）

---

灾后重建

看到那个 n<200 可能就可以用弗洛伊德了

这题主要就是和用重建完成的村庄更新之前的最短路（就像弗洛伊德算法的思想，用 k 更新 i 到 j 的最短路），对于每一个询问时间就往后推，到询问时间为止，再判断是否连通然后输出。实际处理上还行，输入保证t由小到大递增非常省事

更多对着代码想想，这题算法思想还行

代码如下

#include<cstdio>

#include<iostream>

using namespace std;

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

inline void update(int k)

{

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

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

    {

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

        f[j][i]=f[i][j];

    }

}//弗洛伊德，这道题的一、、、坑就是这个无向图在这里面也得存两次

int main()

{

    cin>>n>>m;

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

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

    f[i][j]=1e9;

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

    f[i][i]=;

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

    cin>>t[i];

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

    {

        int x,y,z;

        cin>>x>>y>>z;

        f[x][y]=z;

        f[y][x]=z;

    }//读入和初始化结束

    int q;

    cin>>q;

    int now=;

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

    {

        int x,y,z;

        cin>>x>>y>>z;

        while (now<n&&t[now]<=z)

        {

            update(now);

            now++;

        }//到当前时间点所有最短路更新完毕

        if (t[x]>z||t[y]>z) cout<<"-1"<<endl;

        else if (f[x][y]==1e9) cout<<"-1"<<endl;

        //判断两种无法走到的情况（放在一起判断会WA！！）

        else cout<<f[x][y]<<endl;

    }

    return ;

}

结束，就是这样短短49行（你码风比我好的话会更短 

好的就是这些

ありがとうございます