Problem1086--「一本通 3.3 练习 3」Easy SSSP

1086: 「一本通 3.3 练习 3」Easy SSSP

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:Vijos P1053

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

如果存在负权回路,只输出一行 −1-11;如果不存在负权回路,再求出一个点S到每个点的最短路的长度。约定:SSSSSS 的距离为 000,如果 SSS 与这个点不连通,则输出NoPath。


Input

第一行三个正整数,分别为点数 NNN,边数 MMM,源点 SSS

以下 MMM 行,每行三个整数 a,b,ca, b, ca,b,c,表示点 a,ba, ba,b 之间连有一条边,权值为 ccc


Output

如果存在负权环,只输出一行 −1-11,否则按以下格式输出:

NNN 行,第 iii 行描述 SSS 点到点 iii 的最短路:

  • 如果 SSSiii 不连通,输出NoPath;
  • 如果 i=Si = Si=S,输出 000
  • 其他情况输出 SSSiii 的最短路的长度。

Sample Input

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

Sample Output

0
6
4
-3
-2
7

HINT

对于全部数据,2≤N≤1000,1≤M≤105,1≤a,b,S≤N,∣c∣≤1062\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^62N1000,1M105,1a,b,SN,c106

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


Source/Category


Submit Status