问题 J: 最短路径d

问题 J: 最短路径d

时间限制: 1 Sec  内存限制: 256 MB
提交: 24  解决: 4
[状态] [提交] [命题人:]

题目描述

已知N个点（编号1~N），M条单向边。边的权值可以是负数。如果存在负环，则输出“wrong”,否则求源点S到其余各点的最短路径（不包括到自己），输出其中的最大值。


输入

第一行输入N，M，S。

接下来M行，每行3个整数，Si, Ti, Vi分别表示 点Si 到 Ti之间有长度为Vi的单向边。

输出

若存在负环，则输出“wrong”,否则输出一个整数，表示以S为起点，到达其余N-1个点的最短路径中的最大的那一个值。

样例输入 Copy 

3 3 1
1 2 -1
2 3 -3
3 1 -4

样例输出 Copy 

wrong

提示

无负环的情况：
N<=100000
M<=150000
有负环的情况，数据量较小。


[提交][状态]