6472: 【模板】Floyd
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:9
Solved:2
Description
给出一张由 个点 条边组成的无向图。
求出所有点对 之间的最短路径。
Input
第一行为两个整数 ,分别代表点的个数和边的条数。
接下来 行,每行三个整数 ,代表 之间存在一条边权为 的边。
Output
输出 行每行 个整数。
第 行的第 个整数代表从 到 的最短路径。
如果两点间不存在路径,输出-1
Sample Input Copy
4 4
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output Copy
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
HINT
对于 的数据,,,任意一条边的权值 是正整数且 。
数据中可能存在重边。