Home => ProblemSet => 5.1-19:spfa判断负环
Problem1364--5.1-19:spfa判断负环

1364: 5.1-19:spfa判断负环

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。

Input

第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

Output

如果图中存在负权回路，则输出“Yes”，否则输出“No”。

Sample Input Copy 

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

Sample Output Copy 

Yes

HINT

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过10000。

Source/Category

数据结构 图 spfa 最短路 
[ Submit ] [ Status ]