HUSTOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
1626: 负环判断
内存限制:128 MB
时间限制:1.000 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:3
通过:3
提交
提交记录
统计
Web Board
题目描述
给定一个
n
n
n
个点的有向图,请求出图中是否存在**从顶点
1
1
1
出发能到达**的负环。
负环的定义是:一条边权之和为负数的回路。
输入格式
**本题单测试点有多组测试数据**。
输入的第一行是一个整数
T
T
T
,表示测试数据的组数。对于每组数据的格式如下:
第一行有两个整数,分别表示图的点数
n
n
n
和接下来给出边信息的条数
m
m
m
。
接下来
m
m
m
行,每行三个整数
u
,
v
,
w
u, v, w
u
,
v
,
w
。
- 若
w
≥
0
w \geq 0
w
≥
0
,则表示存在一条从
u
u
u
至
v
v
v
边权为
w
w
w
的边,还存在一条从
v
v
v
至
u
u
u
边权为
w
w
w
的边。
- 若
w
<
0
w < 0
w
<
0
,则只表示存在一条从
u
u
u
至
v
v
v
边权为
w
w
w
的边。
输出格式
对于每组数据,输出一行一个字符串,若所求负环存在,则输出 `YES`,否则输出 `NO`。
输入样例
复制
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
输出样例
复制
NO YES
数据范围与提示
#### 数据规模与约定
对于全部的测试点,保证:
-
1
≤
n
≤
2
×
1
0
3
1 \leq n \leq 2 \times 10^3
1
≤
n
≤
2
×
1
0
3
,
1
≤
m
≤
3
×
1
0
3
1 \leq m \leq 3 \times 10^3
1
≤
m
≤
3
×
1
0
3
。
-
1
≤
u
,
v
≤
n
1 \leq u, v \leq n
1
≤
u
,
v
≤
n
,
−
1
0
4
≤
w
≤
1
0
4
-10^4 \leq w \leq 10^4
−
1
0
4
≤
w
≤
1
0
4
。
-
1
≤
T
≤
10
1 \leq T \leq 10
1
≤
T
≤
1
0
。
#### 提示
请注意,
m
m
m
**不是**图的边数。
分类标签
bellman-ford
SPFA算法