题解 P1119 【灾后重建】

## P1119 【灾后重建】 ### 一道非常好的Floyd最短路练习题，从算法本质上出的题目，对于初学Floyd算法的人来说是绝佳的练习题 ### 解题难度：普及+/提高 ### 重要程度：提高+/省选- ------------ 首先我们从Floyd算法谈起，这是一个看上去很简单的算法-事实上也的确很简单，整个算法一共只有五行，三重循环＋一个判断就能求出图中任意两点之间的最短路径。 很多人都是直接把这个算法背了下来，然后要求最短路时直接默写，没有考虑到这个算法的本质意义，而这个题目，正好考了这个算法的本质，如果只会背的话，遇见这题直接就GG。 这个算法的主要思路，就是通过其他的点进行中转来求的两点之间的最短路。因为我们知道，两点之间有多条路，如果换一条路可以缩短距离的话，就更新最短距离。而它最本质的思想，就是用其他的点进行中转，从而达到求出最短路的目的。 ------------ 那么，如何进行中转呢？两点之间可以由一个点作为中转点更新最短路径，也可以通过多个点更新最短路径。 结合代码： ```cpp 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算法就是一个利用其它点进行中转来求最短路的步骤。 而我们再回头看题意： 所有的边全部给出，**按照时间顺序更新每一个可用的点**（即修建好村庄），对于每个时间点进行两点之间询问，求**对于目前建设的所有村庄**来说**任意两点之间的最短路** **不正好就是Floyd算法中使用前k个节点更新最短路的思维吗？** ------------ 于是到了这里，我们差不多也就知道这题如何写了。 出题人还是很良心的，保证所有的数据都是用时间顺序给出的，所以我们只用读取+操作就可以了，不用再储存＋排序。 先给出总体思路： ``` int main(){ 读入，存下每个村庄修复的时间 读入所有的边并使用邻接矩阵存图 初始化 对于每次询问，将在当前时间前的所有点全部用Floyd更新。 特殊判断并输出 } ``` 具体实现：（仍然按我写题解的风格分开给出） 首先是初始化部分，相信大家都会写 （特别注意一下这里的点编号是从0开始的，如果像我一样习惯从1开始的标下标的话要特别注意这一点） ~~不过这点写错了样例都过不了还是能很快改过来的吧~~ ```cpp //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;//输出路径长 } } ``` **(本题核心) updata函数：** ```cpp 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; } ``` 标准的Floyd思想，内层循环不变，外层循环按照k的顺序给出 ```cpp return 0 //没错，完了，没了，就两个步骤加一个函数. ``` 希望各位能通过这个题目更深一层地了解Floyd算法，这真的是一个很优秀的题目。同时它也提醒我们，学习算法时要弄懂各个细节，把整个算法的思想掌握，而不是仅仅把代码背下来. ------------ ### 参考资料：[GumpYan在博客中对Floyd算法的讲解](https://www.cnblogs.com/GumpYan/p/5540549.html) （侵删） (这篇文章对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; } ```