Đỉnh Bị Ảnh Hưởng Bởi Chu Trình Âm

Buổi 41 — SPFA & Bellman-Ford
Points
38
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ố. Xuất phát từ đỉnh 1, hãy tìm tất cả các đỉnh v mà đường đi ngắn nhất từ 1 đến v có giá trị âm vô cùng (-∞), tức là tồn tại đường đi từ 1 đến v đi qua một chu trình âm.

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.
Dữ liệu ra
  • Dòng đầu tiên in ra số lượng đỉnh tìm được.
  • Nếu số lượng > 0, dòng thứ hai in ra chỉ số các đỉnh đó theo thứ tự tăng dần, cách nhau bởi dấu cách.
Ví dụ
Input Output
5 5
1 2 1
2 3 -3
3 2 1
3 4 5
1 5 2
3
2 3 4
4 3
1 2 5
3 4 -2
4 3 1
0
Giới hạn
  • 1 ≤ N ≤ 2000
  • 0 ≤ M ≤ 5000
  • 1 ≤ u, v ≤ N
  • -10^9 ≤ w ≤ 10^9
Draft saved