题目1447:最短路 {最短路径问题}

发布时间:2016-12-9 12:17:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"题目1447:最短路 {最短路径问题}",主要涉及到题目1447:最短路 {最短路径问题}方面的内容,对于题目1447:最短路 {最短路径问题}感兴趣的同学可以参考一下。

题目描述: 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗? 输入: 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。 当输入为两个0时,输入结束。 输出: 对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间。 样例输入: 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 样例输出: 3 2 代码: #include <stdio.h> int ans[101][101]; void getShortest(int n) { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(ans[i][k] == -1 || ans[k][j] == -1) continue; if(ans[i][j] == -1 || ans[i][k]+ans[k][j] < ans[i][j]) ans[i][j] = ans[i][k] + ans[k][j]; } } int main() { int n,m; while(scanf("%d %d",&n,&m)!=EOF) { if(n == 0 && m==0) break; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) ans[i][j] = -1; ans[i][i] = 0; } int a,b,c; for(int i=1;i<=m;i++) { scanf("%d %d %d",&a,&b,&c); ans[a][b] = ans[b][a] = c; } getShortest(n); printf("%d\n",ans[1][n]); } return 0; } 最短路径: 1.定义:寻找图中某两个特定结点间最短的路径长度 2.Floyd算法。 使用邻接矩阵保存图,此时edge[i][j]的值表示从结点i到结点j,中间不经过任何结点时距离的最小值。 假设结点的编号为1到N,更一般的情况,若edge[i][j]表示从结点i到结点j,中间只能经过编号小于k的点时的最短路径长度, 我们确定edge[i][k] + edge[j][k]的值与edge[i][j]的值,若前者较小则该值代表了新情况中从结点i到结点j的最短路径长度; 否则,该路径长度保持不变。 依次为中间允许经过的结点添加结点1,结点2.。。。。直到结点N,完成后,从结点i都结点j允许经过所有结点的最短路径长度就可以确定了。 代码如下: for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(ans[i][k] == 无穷大 || ans[k][j] == 无穷大) continue; if(ans[i][j] == 无穷大 || ans[i][k]+ans[k][j] < ans[i][j]) ans[i][j] = ans[i][k] + ans[k][j]; } 3.Floyd算法特点。 ①算法复杂度为O(N^3),一般求解的图的大小不超过200个结点,否则可能超时。 ②该算法是利用一个二维矩阵进行相关计算的。注意若图中两个结点之间有多余的边时,我们将边权最小的存入。 ③算法完成后,所有结点间的最短路径长度都确定了。

上一篇:第七章 进程管理
下一篇:在drawable文件中如何画圆

相关文章

相关评论