题目大意：用邻接矩阵给出图中各点的直接距离，计算各个点之间的最短路程，并把这条路输出来。

输入测试

4
1000 5 1000 1000
50 1000 15 5
30 1000 1000 15
15 1000 5 1000

输出结果

i -> j	Dis	Path
1 -> 2	5	1 -> 2
1 -> 3	15	1 -> 2 -> 4 -> 3
1 -> 4	10	1 -> 2 -> 4
2 -> 1	20	2 -> 4 -> 1
2 -> 3	10	2 -> 4 -> 3
2 -> 4	5	2 -> 4
3 -> 1	30	3 -> 1
3 -> 2	35	3 -> 1 -> 2
3 -> 4	15	3 -> 4
4 -> 1	15	4 -> 1
4 -> 2	20	4 -> 1 -> 2
4 -> 3	5	4 -> 3

解题思路

n个点，可以用n次迪杰斯特拉，但不如弗洛伊德算法方便。

如果用弗洛伊德算法求多源最短路径？在最外层枚举路径中间编号最大的点k，接着里面嵌套循环枚举图上两两互不相同的点i和j，如果i->k加上k->j比i->j更短，那么更新i->j的距离，此时，i->k和k->i的距离是已知的，因为i->k和k->j中间的所有点，都不比k大，任意两点路径上的点都比k小的最短路已经上之前算出来了。

如何记录路径？用一个二维数组mp[i][j]记录i到j的路径上前一个点是谁，如果这个点是x，那么接下来求的上一个点就是mp[i][x]。如果更新？如果找到更短路，中间点是k，即i->k->j，那么i->j路上j的前驱就是k->j路上的j的前驱。

不管是无向图，还是有向图，都适用，即使你要判断两点的连通性，也是可以的，如把mp数组改成布尔型，用位运算更新连通性，或者根据距离是否inf判断是否连通。

程序实现