Phát Hiện Chu Trình Âm
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số. Hãy kiểm tra xem đồ thị có tồn tại bất kỳ chu trình âm nào hay không (chu trình có tổng trọng số các cạnh nhỏ hơn 0, không nhất thiết phải đi được từ đỉnh 1).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên N và M.
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả cạnh có hướng từ u đến v với trọng số w.
Dữ liệu ra
- In ra
YESnếu tồn tại ít nhất một chu trình âm, ngược lại in raNO.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 5 2 3 1 3 4 1 4 2 -3 |
YES |
| 3 3 1 2 2 2 3 -2 3 1 0 |
NO |
Giới hạn
- 1 ≤ N ≤ 2000
- 0 ≤ M ≤ 5000
- 1 ≤ u, v ≤ N
- -10^9 ≤ w ≤ 10^9
Community Discussion