LG#B3647. 【模板】Floyd

【模板】Floyd

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条边的带权无向连通图,顶点编号为 1∼n1\sim n,边权均为正整数。图中可能存在重边。

\hspace{15pt}请计算所有顶点对之间的最短路径长度。路径长度为所经过边权之和,顶点到自身的最短距离为 00。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(1\leqq n\leqq100;\ 1\leqq m\leqq4500\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq w_i\leqq10^3\right)$,代表一条无向边。

\hspace{15pt}保证图连通,允许重边。

输出格式

\hspace{15pt}输出 nn 行,每行 nn 个整数。第 ii 行第 jj 个数代表从顶点 ii 到顶点 jj 的最短距离,相邻整数以空格分隔。

测试样例

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 解释

\hspace{15pt}四个顶点形成边长均为 11 的环。相邻顶点距离为 11,相对顶点距离为 22,到自身距离为 00,因此得到样例中的距离矩阵。

2 2
1 2 1
1 2 10
0 1
1 0