题目描述

如何求任意两点之间最短路径呢？

floyd是一个只有5行的算法 他能告诉你一张图中任意两点之间最短路径 这里我们要求的就是任意两个城市之间的最短路

for(k=1;k     for(i=1;i         for(j=1;j             if(e[i][j]>e[i][k]+e[k][j])                  ？？？ 以上代码将最关键的一句去除，如果你想不通，请看看下面这个解释

我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短， 只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。

如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？ 只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。 e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1~n循环，j也是1~n循环，代码实现如下。 for(i=1;i e[i][1]+e[1][j] ) {       e[i][j] = e[i][1]+e[1][j]; }

最后允许通过所有顶点作为中转，任意两点之间最终的最短路程就求出来了

输入格式

输入两个整数n和m，中间用空格隔开，代表城市个数和道路条数(1 后面m行,每行输入三个整数a,b,c，中间用空格隔开 表示 a到b的距离为c   ( 1

题目保证每次的a b不会重复 

注意，这里仅仅指a到b有路，但b到a没有 有多个输入样例

输出格式

输出n*n的二维矩阵 第1行第2列代表从城市1去往城市2的距离，以此类推 若是行列相同则输出0 若是无法相通则输出0x3f3f3f3f的10进制表达式 (既int a=0x3f3f3f3f) 中间用空格隔开，每行末尾无空格

输出矩阵后用空格分开

4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 3
5 10
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 3
5 1 12
5 2 7

0 2 5 4
9 0 3 4
6 8 0 1
5 7 10 0

0 2 5 4
9 0 3 4
6 8 0 1
5 7 3 0

0 2 5 4 1061109567
9 0 3 4 1061109567
6 8 0 1 1061109567
5 7 3 0 1061109567
12 7 10 11 0

提示

出题人：Dash_Guo郭程 计算1801