Điểm Số Tối Đa Đến Đích
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
Community Discussion