Điểm Số Tối Đa Đến Đích

Buổi 41 — SPFA & Bellman-Ford
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Trò chơi gồm N phòng và M đường hầm một chiều. Khi đi qua đường hầm từ u đến v, điểm số của bạn thay đổi một lượng w (w có thể dương hoặc âm). Bạn bắt đầu ở phòng 1 với 0 điểm và cần đi đến phòng N. Hãy tìm điểm số lớn nhất có thể khi đến phòng N.

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
  • In ra điểm số lớn nhất có thể khi đến N.
  • Nếu có thể tăng điểm lên dương vô cùng trên đường đi từ 1 đến N, in ra INF.
  • Nếu không thể đi từ 1 đến N, in ra UNREACHABLE.
Ví dụ
Input Output
4 5
1 2 3
2 4 -1
1 3 2
3 4 4
1 4 5
6
4 4
1 2 1
2 3 2
3 2 -1
3 4 5
INF
Giới hạn
  • 1 ≤ N ≤ 2500
  • 0 ≤ M ≤ 5000
  • 1 ≤ u, v ≤ N
  • -10^9 ≤ w ≤ 10^9
Draft saved