← 返回题目
题库练习 【模板】全源最短路
← 上一题 下一题 →

A4931 | 【模板】全源最短路

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个包含 $n$ 个顶点和 $m$ 条有向边的带权图，请计算图中所有顶点对之间的最短路径距离。

### 图的性质
- 图中可能存在**负权边**
- 图中可能存在**重边**和**自环**
- 需要检测图中是否存在**负权回路**（负环）

输入格式

**输入数据共 $m+1$ 行**：

- 第 1 行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。
- 接下来 $m$ 行，每行包含三个整数 $u$, $v$, $w$，表示存在一条从顶点 $u$ 指向顶点 $v$ 的有向边，边权为 $w$。

输出格式

**根据图中是否存在负环，输出不同内容**：

1. **如果存在负环**：
- 仅输出一行 -1

2. **如果不存在负环**：
- 输出 $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
C++ 编辑器
输入
输出