Phát Hiện Chu Trình Âm

Buổi 41 — SPFA & Bellman-Ford
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 YES nếu tồn tại ít nhất một chu trình âm, ngược lại in ra NO.
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
Draft saved