A4931. 【模板】全源最短路
编程题
普及/提高-
知识点
题目描述
给定一个包含 $n$ 个顶点和 $m$ 条有向边的带权图，请计算图中所有顶点对之间的最短路径距离。
### 图的性质
- 图中可能存在**负权边**
- 图中可能存在**重边**和**自环**
- 需要检测图中是否存在**负权回路**（负环）
### 图的性质
- 图中可能存在**负权边**
- 图中可能存在**重边**和**自环**
- 需要检测图中是否存在**负权回路**（负环）
输入格式
**输入数据共 $m+1$ 行**：
- 第 1 行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。
- 接下来 $m$ 行，每行包含三个整数 $u$, $v$, $w$，表示存在一条从顶点 $u$ 指向顶点 $v$ 的有向边，边权为 $w$。
- 第 1 行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。
- 接下来 $m$ 行，每行包含三个整数 $u$, $v$, $w$，表示存在一条从顶点 $u$ 指向顶点 $v$ 的有向边，边权为 $w$。
输出格式
**根据图中是否存在负环，输出不同内容**：
1. **如果存在负环**：
- 仅输出一行
2. **如果不存在负环**：
- 输出 $n$ 行，每行 $n$ 个整数
- 第 $i$ 行第 $j$ 个数表示顶点 $i$ 到顶点 $j$ 的最短距离 $dis(i,j)$
- 如果顶点 $i$ 无法到达顶点 $j$，则 $dis(i,j) = 10^9$
- 特别地，$dis(i,i) = 0$（顶点到自身的距离为 0）
1. **如果存在负环**：
- 仅输出一行
-12. **如果不存在负环**：
- 输出 $n$ 行，每行 $n$ 个整数
- 第 $i$ 行第 $j$ 个数表示顶点 $i$ 到顶点 $j$ 的最短距离 $dis(i,j)$
- 如果顶点 $i$ 无法到达顶点 $j$，则 $dis(i,j) = 10^9$
- 特别地，$dis(i,i) = 0$（顶点到自身的距离为 0）
输入输出样例
输入 #1
5 7 1 2 4 1 4 10 2 3 7 4 5 3 4 2 -2 3 4 -3 5 3 4
输出 #1
0 4 11 8 11 1000000000 0 7 4 7 1000000000 -5 0 -3 0 1000000000 -2 5 0 3 1000000000 -1 4 1 0
输入 #2
5 5 1 2 4 3 4 9 3 4 -3 4 5 3 5 3 -2
输出 #2
-1
说明/提示
**样例1说明**：
- 输出的是一个 $5 \times 5$ 的最短距离矩阵
- 例如 $dis(1,3)=11$ 表示顶点1到顶点3的最短距离为11
- $dis(3,2)=-5$ 表示顶点3到顶点2的最短距离为-5（存在负权边）
- 所有无法到达的点对距离均为 $10^9$
**样例2说明**：
- 图中存在一个负权回路（3→4→5→3），该回路的权值和为-2，因此输出-1
## 数据范围
- **顶点数**：$1 \leq n \leq 500$
- **边数**：$1 \leq m \leq 1000$
- **边权范围**：$-3 \times 10^5 \leq w \leq 3 \times 10^5$
- **特殊性质**：20%的数据保证不存在负权边
- 输出的是一个 $5 \times 5$ 的最短距离矩阵
- 例如 $dis(1,3)=11$ 表示顶点1到顶点3的最短距离为11
- $dis(3,2)=-5$ 表示顶点3到顶点2的最短距离为-5（存在负权边）
- 所有无法到达的点对距离均为 $10^9$
**样例2说明**：
- 图中存在一个负权回路（3→4→5→3），该回路的权值和为-2，因此输出-1
## 数据范围
- **顶点数**：$1 \leq n \leq 500$
- **边数**：$1 \leq m \leq 1000$
- **边权范围**：$-3 \times 10^5 \leq w \leq 3 \times 10^5$
- **特殊性质**：20%的数据保证不存在负权边