Tìm Chu Trình Âm

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh. Xác định xem đồ thị có chu trình âm không. Nếu có, in một chu trình âm bất kỳ.

Dòng 1: hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$ , $b$ , $c$ — cạnh có hướng từ $a$ đến $b$ với trọng số $c$ .

Nếu không có chu trình âm: in NO.
Nếu có chu trình âm: in YES, rồi in các đỉnh của chu trình theo thứ tự (đỉnh đầu và đỉnh cuối giống nhau).

Input	Output	Giải thích
4 5 1 2 1 2 4 1 3 1 1 4 1 -3 4 3 -2	YES 1 2 4 1	Chu trình 1→2→4→1: tổng 1+1+(-3)=-1 < 0.

Bình luận

Không có bình luận tại thời điểm này.