Chu trình chênh lệch

Buổi 67-68 — Mock IOI
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved