LG#B3647. 【模板】Floyd
【模板】Floyd
题目描述
给定一个有 个顶点、 条边的带权无向连通图,顶点编号为 ,边权均为正整数。图中可能存在重边。
请计算所有顶点对之间的最短路径长度。路径长度为所经过边权之和,顶点到自身的最短距离为 。
输入格式
第一行输入两个整数 $n,m\left(1\leqq n\leqq100;\ 1\leqq m\leqq4500\right)$。
此后 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq w_i\leqq10^3\right)$,代表一条无向边。
保证图连通,允许重边。
输出格式
输出 行,每行 个整数。第 行第 个数代表从顶点 到顶点 的最短距离,相邻整数以空格分隔。
测试样例
4 4
1 2 1
2 3 1
3 4 1
4 1 1
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
样例 1 解释
四个顶点形成边长均为 的环。相邻顶点距离为 ,相对顶点距离为 ,到自身距离为 ,因此得到样例中的距离矩阵。
2 2
1 2 1
1 2 10
0 1
1 0