灾后重建-题解

查看原题请戳这里

这道题目考查的就是对Folyd的灵活运用

因为这题是需要你去求多元最短路，所以用Dijkstra或SPFA的话，时间复杂度显然是不可以接收的。 当然了，如果你直接用Floyd的话，也是会超时的。所以这道题就需要我们掌握Floyd的原理，才可以解决掉。

那么，我们该怎么去做呢？

我们会发现，这道题目每个村庄修好的时间是不一致的，根据Floyd的思想，对于每一个新的查询时间t，我们只需要用在第k天修好的村庄去更新其它村庄的最短路即可。 在更新的过程中，我们会发现我们枚举的i，j两个点可能是尚未修复的，但这并没有关系，因为安照我们的算法思路，未被修复的村庄是不会被拿来更新其它村庄的距离的，而对于这两个村庄，我们只需要在读入时特判一下即可。 附一下代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define INF 1000000000

using namespace std;
int n,m,q,cnt,x,y,t,T,fi[300],head[300],map[300][300];
struct Edge{
    int to,next,x;
}edge[100005];
void floyd(int k)
{
    for(register int i = 1; i <= n; i++)
        for(register int j = 1; j <= n; j++)
            map[i][j] = min(map[i][j],map[i][k] + map[k][j]);
}
int main()
{
    scanf(“%d%d”,&n,&m);
    for(register int i = 1; i <= n; i++)
        for(register int j = 1; j <= n; j++)
            map[i][j] = INF;
    for(register int i = 1; i <= n; i++) scanf(“%d”,&fi[i]);
    for(register int i = 1; i <= m; i++)
    {
        scanf(“%d%d%d”,&x,&y,&t);
        x ++; y ++;  //个人习惯存的点的边号为1n，而题目给出的是0n-1
        map[x][y] = t;
        map[y][x] = t;
    }
    scanf(“%d”,&q);
    T = 0;
    for(register int a = 1; a <= q; a++)
    {
        scanf(“%d%d%d”,&x,&y,&t);
        x ++; y ++;
        while(t >= fi[T + 1] && T < n)
        {
            T++;
            floyd(T);
        }
        if(fi[x] > t || fi[y] > t || map[x][y] == INF)
        {
            printf(“-1\n”);
            continue ;
        }
        printf(“%d\n”,map[x][y]);
    }
    return 0;
}