【模板】Floyd算法

题目描述:

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

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

输入格式:

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

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

输出格式:

输出 \(n\) 行每行 \(n\) 个整数。

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

样例输入:

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\%\) 的数据，\(n \le 100\)，\(m \le 4500\)，任意一条边的权值 \(w\) 是正整数且 \(1 \leqslant w \leqslant 1000\)。

**数据中可能存在重边。**

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创