#Psp12. 【例题2】判断负环
【例题2】判断负环
【例题2】判断负环
题目描述
给定一个n个点的有向图,请求出图中是否存在从顶点1出发能到达的负环。
负环的定义是:一条边权之和为负数的回路。
输入格式
输入的第一行是一个整数T,表示测试数据的组数。对于每组数据的格式如下:
第一行有两个整数,分别表示图的点数n和边数m。
接下来m行,每行三个整数u,v,w。
若w>=0,则表示存在一条从u至v边权为w的边,还存在一条从v至w\u边权为w的边。
若w<0,则只表示存在一条从u至v边权为w的边。
输出格式
输出格式
对于每组数据,输出一行一个字符串,若所求负环存在,则输出YES,否则输出N0。
数据范围
(原站未提供,导入后需人工补齐)
样例
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
N0
YES
提示
$对于100%的数据,满足1<=n<=2*10^3,1<=m<=3*10^3,1<=u,v<=n,-10^4<=w<=10^4,1<=T<=10$。