问题1930--Johnson 全源最短路

1930: Johnson 全源最短路

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

输入

输出

样例输入 Copy 

5 7
1 2 4
1 4 10
2 3 7
4 5 3
4 2 -2
3 4 -3
5 3 4

样例输出 Copy 

128
1000000072
999999978
1000000026
1000000014

提示


上图为样例 1 给出的有向图，最短路构成的答案矩阵为：


来源/分类

最短路径 SPFA算法 Dijkstra算法 Floyd算法 
[提交] [状态]