3553 - spfa判断负环2

题目描述

给定一个 n 个点、 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

请你判断图中是否存在负权回路。

输入

第一行包含整数 n m

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

输出

如果图中存在负权回路,则输出 Yes,否则输出 No

样例

输入

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

输出

Yes
说明

提示

1 \leq n \leq 20000 1 \leq m \leq 200000 ,图中涉及边长绝对值均不超过 10000。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 14
通过人数 8
金币数量 3 枚
难度 基础


上一题 下一题