P1119 【灾后重建】

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4
-1
-1
5
4

一道非常好的Floyd最短路练习题,从算法本质上出的题目,对于初学Floyd算法的人来说是绝佳的练习题

首先我们从Floyd算法谈起,这是一个看上去很简单的算法-事实上也的确很简单,整个算法一共只有五行,三重循环+一个判断就能求出图中任意两点之间的最短路径。
很多人都是直接把这个算法背了下来,然后要求最短路时直接默写,没有考虑到这个算法的本质意义,而这个题目,正好考了这个算法的本质,如果只会背的话,遇见这题直接就GG。
这个算法的主要思路,就是通过其他的点进行中转来求的两点之间的最短路。因为我们知道,两点之间有多条路,如果换一条路可以缩短距离的话,就更新最短距离。而它最本质的思想,就是用其他的点进行中转,从而达到求出最短路的目的。

那么,如何进行中转呢?两点之间可以由一个点作为中转点更新最短路径,也可以通过多个点更新最短路径。
结合代码:

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

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

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

            if(e[i][j]>e[i][k]+e[k][j])

                 e[i][j]=e[i][k]+e[k][j];
                 
//核心代码,仅仅只有5行

这段代码的基本思想就是:最开始只允许经过1号顶点进行中转,接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转,求任意两点之间的最短路程。用一句话概括就是:从i号顶点到j号顶点只经过前k号点的最短路程。
(仔细理解这段话,它揭露了这个算法的本质并为本题提供了很好的方法)
到这里我们已经知道,Floyd算法就是一个利用其它点进行中转来求最短路的步骤。
而我们再回头看题意:
所有的边全部给出,按照时间顺序更新每一个可用的点(即修建好村庄),对于每个时间点进行两点之间询问,求对于目前建设的所有村庄来说任意两点之间的最短路
不正好就是 F l o y d Floyd Floyd算法中使用前k个节点更新最短路的思维吗?

于是到了这里,我们差不多也就知道这题如何写了。
出题人还是很良心的,保证所有的数据都是用时间顺序给出的,所以我们只用读取+操作就可以了,不用再储存+排序。
先给出总体思路:

int main(){
    读入,存下每个村庄修复的时间
    读入所有的边并使用邻接矩阵存图
    初始化
    对于每次询问,将在当前时间前的所有点全部用Floyd更新。
    特殊判断并输出
}

具体实现:(仍然按我写题解的风格分开给出)
首先是初始化部分,相信大家都会写
(特别注意一下这里的点编号是从0开始的,如果像我一样习惯从1开始的标下标的话要特别注意这一点)
不过这点写错了样例都过不了还是能很快改过来的吧

//a数组存各个村庄的建立时间
//f数组用于存两点之间的最短路径

cin>>n>>m;
    for(int i=0;i<n;i++)
    scanf("%d",a+i);//依次输入每一个村庄建立完成时需要的时间
 /*******************初始化*************************/
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    f[i][j]=1e9;//初始化为一个很大的值
    for(int i=0;i<n;i++)
    f[i][i]=0;//一个点到自己的距离为0
 /*******************读入边长*************************/
    int s1,s2,s3;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&s1,&s2,&s3);
        f[s1][s2]=f[s2][s1]=s3;//无向边,存两次
    }

然后是处理各询问:

//s1,s2,s3为临时变量,表示两村庄和时间
int q;cin>>q;//一共q个询问
int now=0;//用于记录当前时间对应的编号,从第一个村庄开始
for(int i=1;i<=q;i++){//处理各询问 
    scanf("%d%d%d",&s1,&s2,&s3);
    while(a[now]<=s3&&now<n){//如果目前更新的点的时间在询问点之前
        updata(now);
        now++;
    }//处理在它之前建立的村庄
    if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;//村庄未建好
    else {
        if(f[s1][s2]==1e9)cout<<-1<<endl;//两点不连通
        else cout<<f[s1][s2]<<endl;//输出路径长
    }
}

(本题核心) u p d a t a updata updata函数:

inline void updata(int k){
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(f[i][j]>f[i][k]+f[j][k])
    f[i][j]=f[j][i]=f[i][k]+f[j][k];//用这个新的更新所有前面的 
    return;
}

标准的 F l o y d Floyd Floyd思想,内层循环不变,外层循环按照 k k k的顺序给出

  return 0
    //没错,完了,没了,就两个步骤加一个函数.

希望各位能通过这个题目更深一层地了解 F l o y d Floyd Floyd算法,这真的是一个很优秀的题目。同时它也提醒我们,学习算法时要弄懂各个细节,把整个算法的思想掌握,而不是仅仅把代码背下来.

参考资料:GumpYan在博客中对Floyd算法的讲解

(这篇文章对 F l o y d Floyd Floyd算法进行了图文并茂的很详细的讲解,如果想更详细地了解此算法可以去看看)

最后放上完整的AC代码。

#include<iostream>
#include<cstdio>
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];//邻接矩阵存边
inline void updata(int k){
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(f[i][j]>f[i][k]+f[j][k])
    f[i][j]=f[j][i]=f[i][k]+f[j][k];//用这个新的更新所有前面的 
    return;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
    scanf("%d",a+i);//依次输入每一个村庄建立完成时需要的时间
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        f[i][j]=1e9;//初始化为保证它不爆炸范围内的最大值 
    }
    for(int i=0;i<n;i++)
    f[i][i]=0;
    int s1,s2,s3;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&s1,&s2,&s3);
        f[s1][s2]=f[s2][s1]=s3;//初始化边长 
    }
    int q;
    cin>>q;
    int now=0;
    for(int i=1;i<=q;i++){//处理各询问 
        scanf("%d%d%d",&s1,&s2,&s3);
        while(a[now]<=s3&&now<n){
            updata(now);//依次更新点,使它可以被用来更新其他的点 
            now++;
        }
        if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;
        else {
            if(f[s1][s2]==1e9)cout<<-1<<endl;
            else cout<<f[s1][s2]<<endl;
        }
    }
    return 0;
} 

来源