【信奥教学】_CSP_S_算法之 Floyd 找最小环

【模板】Floyd

题目描述

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

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

输入格式

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

接下来 m 行，每行三个整数 $u,v,w$，代表 $u,v$ 之间存在一条边权为 $w$ 的边。

输出格式

输出 $n$ 行每行 $n$ 个整数。

第 $i$ 行的第 $j$ 个整数代表从 $i$ 到 $j$ 的最短路径。

样例 #1

样例输入 #1

4 4

1 2 1

2 3 1

3 4 1

4 1 1样例输出 #1

0 1 2 1

1 0 1 2

2 1 0 1

1 2 1 0提示

对于 100% 的数据，n <= 100，m <= 4500，任意一条边的权值 w 是正整数且 1 <= w <= 1000。

数据中可能存在重边。