#B3647. 【模板】Floyd 算法

【模板】Floyd 算法

题目描述

给出一张由 nn 个点 mm 条边组成的无向图。

求出所有点对 (i,j)(i,j) 之间的最短路径。

输入格式

第一行为两个整数 n,mn,m,分别代表点的个数和边的条数。

接下来 mm 行,每行三个整数 u,v,wu,v,w,代表 u,vu,v 之间存在一条边权为 ww 的边。

输出格式

输出 nn 行每行 nn 个整数。

ii 行的第 jj 个整数代表从 iijj 的最短路径。

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

提示

对于 100%100\% 的数据,n100,m4500n \le 100 , m \le 4500,任意一条边的权值 ww 是正整数且 1w10001 \leqslant w \leqslant 1000