1050. Easy sssp

时间限制 1000 ms
内存限制 128 MB

题目描述

输入数据给出一个有N(2 < = N < = 1,000)个节点,M(M < = 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 < = S < = N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.

输入数据

第一行: 点数 $N\ (2 \le N \le 1,000), $ 边数 $M\ (M \le 100,000), $ 源点 $S\ (1 \le S \le N);$
以下 $M$ 行, 每行三个整数 $a, b, c$ 表示点 $a, b\ (1 \le a, b \le N)$ 之间连有一条边, 权值为 $c\ (-1,000,000 \le c \le 1,000,000)$

输出数据

如果存在负权环, 只输出一行 $-1, $ 否则按以下格式输出
共 $N$ 行, 第 $i$ 行描述 $S$ 点到点 $i$ 的最短路:
如果 $S$ 与 $i$ 不连通, 输出NoPath;
如果 $i = S, $ 输出 $0;$
其他情况输出 $S$ 到 $i$ 的最短路的长度.

样例输入

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

样例输出

0
6
4
-3
-2
7

样例说明

做这道题时, 你不必为超时担心, 不必为不会算法担心, 但是如此“简单”的题目, 你究竟能ac么?

题目信息

未提交
未通过无法查看
未通过无法查看