1508：Easy SSSP

题目描述

输入数据给出一个有 $N$ 个节点，$M$ 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。

如果存在负权回路，只输出一行 -1；如果不存在负权回路，再求出一个点 $S$ 到每个点的最短路的长度。约定：$S$ 到 $S$ 的距离为 $0$，如果 $S$ 与这个点不连通，则输出 NoPath。

输入格式

第一行三个正整数，分别为点数 $N$，边数 $M$，源点 $S$；

以下 $M$ 行，每行三个整数 $a, b, c$，表示点 $a$ 到点 $b$ 之间连有一条有向边，权值为 $c$。

输出格式

如果存在负权环，只输出一行 -1，否则按以下格式输出：

共 $N$ 行，第 $i$ 行描述 $S$ 点到点 $i$ 的最短路：

• 如果 $S$ 与 $i$ 不连通，输出 NoPath；
• 如果 $i=S$，输出 $0$；
• 其他情况输出 $S$ 到 $i$ 的最短路的长度。

样例

样例输入 #1

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

样例输出 #1

0
6
4
-3
-2
7

样例解释 #1

• 图中没有负权环。
• 从源点 $S=1$ 出发：
  • 到 $1$：$0$
  • 到 $2$：$1 \to 2$，长度 $6$
  • 到 $3$：$1 \to 3$，长度 $4$
  • 到 $4$：$1 \to 3 \to 4$，长度 $4 + (-7) = -3$
  • 到 $5$：$1 \to 3 \to 4 \to 5$，长度 $4 + (-7) + 1 = -2$
  • 到 $6$：$1 \to 3 \to 6$，长度 $4 + 3 = 7$

数据范围

对于全部数据：

• $2 \le N \le 1000$
• $1 \le M \le 10^5$
• $1 \le a, b, S \le N$
• $|c| \le 10^6$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题需要先判断整个图中是否存在负权环（可以用 Bellman-Ford 或 SPFA 判断），如果没有负权环，再计算从源点 $S$ 到所有点的最短路径（注意处理不连通的情况）。由于 $N \le 1000$，$M \le 10^5$，需要选择高效的算法。