hihoCoder 1089 : 最短路径·二：Floyd算法

╰半夏微凉° 2024-02-17 21:36 68阅读 0赞

#### \#1089 : 最短路径·二：Floyd算法 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

##### 描述 #####

万圣节的中午，小Hi和小Ho在吃过中饭之后，来到了一个新的鬼屋！

鬼屋中一共有N个地点，分别编号为1..N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。

由于没有肚子的压迫，小Hi和小Ho决定好好的逛一逛这个鬼屋，逛着逛着，小Hi产生了这样的问题：鬼屋中任意两个地点之间的最短路径是多少呢？

[提示：其实如果你开心的话，完全可以从每个节点开始使用Dijstra算法\_(:з」∠)\_。][Dijstra]

##### 输入 #####

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为2个整数N、M，分别表示鬼屋中地点的个数和道路的条数。

接下来的M行，每行描述一条道路：其中的第i行为三个整数u\_i, v\_i, length\_i，表明在编号为u\_i的地点和编号为v\_i的地点之间有一条长度为length\_i的道路。

对于100%的数据，满足N<=10^2，M<=10^3, 1 <= length\_i <= 10^3。

对于100%的数据，满足迷宫中任意两个地点都可以互相到达。

##### 输出 #####

对于每组测试数据，输出一个N\*N的矩阵A，其中第i行第j列表示，从第i个地点到达第j个地点的最短路径的长度，当i=j时这个距离应当为0。

样例输入

5 12
    1 2 967
    2 3 900
    3 4 771
    4 5 196
    2 4 788
    3 1 637
    1 4 883
    2 4 82
    5 2 647
    1 4 198
    2 4 181
    5 2 665

样例输出

0 280 637 198 394 
    280 0 853 82 278 
    637 853 0 771 967 
    198 82 771 0 196 
    394 278 967 196 0

分析：最短路之Floyd模板题

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 10000000
    const int maxn=1e2+5;
    int N,M;
    int d[maxn][maxn];
    int main(){
    	while(scanf("%d%d",&N,&M)==2){
    		for(int i=1;i<=N;i++)
    		 for(int j=1;j<=N;j++)
    		 if(i==j)d[i][j]=0;
    		 else 
    		 d[i][j]=INF;
    		 
    		for(int i=0;i<M;i++){
    			int u,v,len;
    			scanf("%d%d%d",&u,&v,&len);
    			d[u][v]=d[v][u]=min(len,d[u][v]);
    		}
    		
    		for(int k=1;k<=N;k++){
    			for(int i=1;i<=N;i++){
    				for(int j=1;j<=N;j++){
    					d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    				}
    			}
    		}
    		
    		for(int i=1;i<=N;i++){
    			printf("%d",d[i][1]);
    			for(int j=2;j<=N;j++)
    			printf(" %d",d[i][j]);
    			
    			printf("\n");
    		}
    	}
    	return 0;
    }

[Dijstra]: https://hihocoder.com/problemset/problem/1089#