A5478. 「一本通 3.3 练习 3」Easy SSSP
编程题
提高+/省选-
知识点
题目描述
**原题来自：[Vijos P1053](https://vijos.org/p/1053)**
输入数据给出一个有 $N$ 个节点，$M$ 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 $0$，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 $-1$；如果不存在负权回路，再求出一个点 $S$ 到每个点的最短路的长度。约定：$S$ 到 $S$ 的距离为 $0$，如果 $S$ 与这个点不连通，则输出
输入数据给出一个有 $N$ 个节点，$M$ 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 $0$，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 $-1$；如果不存在负权回路，再求出一个点 $S$ 到每个点的最短路的长度。约定：$S$ 到 $S$ 的距离为 $0$，如果 $S$ 与这个点不连通，则输出
NoPath。输入格式
第一行三个正整数，分别为点数 $N$，边数 $M$，源点 $S$；
以下 $M$ 行，每行三个整数 $a, b, c$，表示点 $a, b$ 之间连有一条边，权值为 $c$。
以下 $M$ 行，每行三个整数 $a, b, c$，表示点 $a, b$ 之间连有一条边，权值为 $c$。
输出格式
如果存在负权环，只输出一行 $-1$，否则按以下格式输出：
共 $N$ 行，第 $i$ 行描述 $S$ 点到点 $i$ 的最短路：
- 如果 $S$ 与 $i$ 不连通，输出
- 如果 $i = S$，输出 $0$。
- 其他情况输出 $S$ 到 $i$ 的最短路的长度。
共 $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
说明/提示
对于全部数据，$2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6$。