链接: https://cses.fi/problemset/task/1196

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个有向图，你的任务是判断其中是否包含负权环，并给出一个这样的环的示例。

输入

第一行输入包含两个整数 $n$ 和 $m$：节点数和边数。节点编号为 $1,2,\ldots,n$。

之后有 $m$ 行描述边。每行包含三个整数 $a$、$b$ 和 $c$：存在一条从节点 $a$ 到节点 $b$ 的边，长度为 $c$。

输出

如果图包含负权环，先输出 "YES"，然后按正确顺序输出环上的节点。如果有多个负权环，你可以输出任意一个。如果没有负权环，输出 "NO"。

数据范围

$1 \le n \le 2500$ $1 \le m \le 5000$ $1 \le a,b \le n$ $-10^9 \le c \le 10^9$

样例输入

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

样例输出

YES
1 2 4 1