Đỉnh Bị Ảnh Hưởng Bởi Chu Trình Âm
Points
38
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ố. 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
Community Discussion