Floyd 最短路 hdu1869 hdu2544

本文主要是介绍Floyd 最短路 hdu1869 hdu2544，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Floyd 算法， 举个例子来理解原理，

如果a 走到 e点，那么，a 可以经过b 走到e ,也可以直接走到e , 但是经过b走到e 只要20 ,而直接走到e要30，所以a 走到e的距离被更新为20。

有三层循环，O(n^3)算法，都是构造这样的短距离，之后每两点之间的距离都是最短的。

先看HDU 1869 题，

/*给不连接的点赋无穷大，然后每两个点都去更新，把两点可走的最短路

都找出来，则时间复杂度O(n^3)*/

/*给不连接的点赋无穷大，然后每两个点都去更新，把两点可走的最短路
都找出来，则时间复杂度O(n^3)*/ #include<stdio.h>
#include<string.h>int map[1005][1005];void floyd(int n)
{for(int k = 0 ; k <= n ; k++ )for(int i = 0 ; i <= n ; i++ )for(int j = 0 ; j <= n ; j++ )     if(map[i][j]>map[i][k]+map[k][j])    //i j 两点，和i 到 k 然后再从 k 到 j  距离的比较。   
map[i][j] = map[i][k]+map[k][j]; //核心代码   
}int jud(int n)
{for(int i = 0 ; i < n ; i++ )for(int j = 0 ; j < n ; j++ )if(map[i][j]>7)return 0 ;return 1;
}int main()
{   int  n , m ; while(scanf("%d%d",&n,&m)!=EOF){memset(map,0x3f,sizeof(map));    //给不连接的点赋无穷大 for(int i = 0 ; i < n ; i++)map[i][i] = 0 ;       //自己与自己无权值 while(m--){int a , b ;scanf("%d%d",&a,&b);map[a][b] = map[b][a] = 1;}floyd(n);if(jud(n))printf("Yes\n");else printf("No\n");}return 0;
}

再看，HDU 2544

#include<stdio.h>
#include<string.h>
#include<stdlib.h>int map[105][105],vis[10005];
int n,m;void Floyd()
{for(int k = 1; k <= n; k++ )for(int i = 1; i <= n; i++ )for(int j = 1; j <= n; j++ ){if(map[i][j]>map[i][k]+map[k][j])map[i][j] = map[i][k]+map[k][j];}
}int main()
{while(scanf("%d%d",&n,&m),n,m){      memset(map,0x3f,sizeof(map));for(int i = 1 ; i <= n ; i++)map[i][i] = 0 ;for(int i = 1 ; i <= m; i++){int a , b , c;scanf("%d%d%d",&a,&b,&c);map[a][b] = map[b][a] = c;}Floyd();printf("%d\n",map[1][n]);}return 0;
}

经过这样构造之后，那么我们可以直接求任意两点的最短距离。

我开始犯了一点小错，因为思想没跟上来，以为所有两点的距离值还保留着，其实任何两个点的值都已经转换成最小值了。

所以第二个题，直接输出map[1][n] 就可以了。

这篇关于Floyd 最短路 hdu1869 hdu2544的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---