Khoảng cách với phụ phí âm

Bối cảnh và bài toán

Một hệ thống điểm thưởng có các cung chi phí có thể âm do hoàn tiền. Không có chu trình âm đi được từ nguồn.

Yêu cầu

Tính khoảng cách ngắn nhất từ s tới mọi đỉnh.

Input

Dòng đầu n, m, s; tiếp theo m cạnh có hướng u, v, w.

Output

In n khoảng cách, dùng INF cho đỉnh không tới được.

Ràng buộc

• 1 <= n <= 2500
• 0 <= m <= 5000
• -10^9 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 100, m <= 300 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 4 1
1 2 4
1 3 5
2 3 -2
3 4 1

Output

0 4 2 3

Giải thích. Relaxation nhiều vòng cho phép cạnh âm lan ảnh hưởng dần theo số cạnh trên đường đi.

Ví dụ 2

Input

3 1 1
1 2 -5

Output

0 -5 INF

Giải thích. Relaxation nhiều vòng cho phép cạnh âm lan ảnh hưởng dần theo số cạnh trên đường đi.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.