题目描述

如果说Floyd是求任意两个点之间的最短距离，那么迪杰斯特拉(dijkstra)就是求一个点到其它点的最短距离(仔细想想不同)

以下引用自CSND博客：https://blog.csdn.net/kprogram/article/details/81225176

1.将图上的初始点看作一个集合S，其它点看作另一个集合 2.根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大） 3.选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S（实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离） 4.再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。 （仔细想想，为啥只更新跟x相邻点的d[y]，而不是更新所有跟集合 s 相邻点的 d 值？ 因为第三步只更新并确定了x点到初始点的最短距离 集合内其它点是之前加入的，也经历过第 4 步，所以与 x 没有相邻的点的 d 值是已经更新过的了，不会受到影响） 5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。  （注：重复第三步的时候，应该从所有的d[i]中寻找最小值，而不是只从与x点相邻的点中寻找。想想为什么？）

伪代码：

清除所有点的标号; 设d[0]=0，其他d[i]=INF;//INF是一个很大的值，用来替代正无穷(我用0x3f3f3f3f) 循环n次  {  在所有未标号结点中，选出d值最小的结点x; 给结点x标记; 对于从x出发的所有边(x,y)，更新d[y] = min{d[y], d[x]+w(x,y)}  }

输入格式

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

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

注意，这里仅仅指a到b有路，但b到a没有

有多个输入样例

输出格式

输出城市1到所有路的最短距离（为1*n的矩阵） 若是自己则输出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 1
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
0 1 4 4
0 2 5 4 1061109567

提示

出题人： Extra_Guo 郭程 计算1801