Chu trình chênh lệch
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh có trọng số (có thể âm, bằng $0$, hoặc dương). Hãy tìm độ dài nhỏ nhất của một hành trình (có thể đi qua đỉnh và cạnh nhiều lần) từ đỉnh $1$ đến đỉnh $N$.
- Nếu không có đường đi từ $1$ đến $N$, in ra
IMPOSSIBLE. - Nếu có thể làm tổng trọng số nhỏ đi vô hạn lần, in ra
-INF. - Ngược lại, in ra tổng trọng số nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 2500$, $0 \le M \le 5000$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $-10^9 \le w \le 10^9$).
Kết quả
In ra IMPOSSIBLE, -INF, hoặc một số nguyên duy nhất là độ dài hành trình nhỏ nhất.
Subtasks
- Subtask 1 (30%): Tất cả trọng số $w \ge 0$.
- Subtask 2 (30%): $N \le 200, M \le 500$.
- Subtask 3 (40%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 3 2 3 -2 3 2 -2 3 4 5 1 4 10 |
-INF |
Community Discussion