#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$。