多源最短路径 模板题

📝 题目描述

给定一张有 \(n\) 个顶点、\(m\) 条边的有向图，图中可能存在重边，但不存在自环。

请你求出任意两点之间的最短路径长度（如果无法到达则输出 -1），输出一个 \(n \times n\) 的矩阵，第 \(i\) 行第 \(j\) 列表示从点 \(i\) 到点 \(j\) 的最短路径长度。

📥 输入格式

第一行两个整数 \(n\) 和 \(m\)，表示图中有 \(n\) 个点和 \(m\) 条边。

接下来 \(m\) 行，每行三个整数 \(u, v, w\)，表示存在一条从点 \(u\) 到点 \(v\) 的有向边，边权为 \(w\)。

• \(1 \le u, v \le n\)
• \(u \ne v\)
• \(1 \le w \le 10^6\)

📤 输出格式

输出 \(n\) 行，每行 \(n\) 个用空格隔开的整数，表示从点 \(i\) 到点 \(j\) 的最短路径长度。

• 如果 \(i = j\)，输出 \(0\)
• 如果 \(i \ne j\) 且 \(i\) 无法到达 \(j\)，输出 -1
• 否则输出从 \(i\) 到 \(j\) 的最短路径权值

💡 样例输入

4 6
1 2 5
1 3 10
2 3 2
3 4 1
4 2 3
2 4 8

✅ 样例输出

0 5 7 8
-1 0 2 3
-1 4 0 1
-1 3 5 0

🔍 提示

• 本题数据规模适合使用 Floyd-Warshall 算法，时间复杂度为 \(O(n^3)\)。
• 图中可能有多条边连接同一对点，请取最小的权值(重边取最小的权重的边)。