Đường đi ngắn nhất với trọng số âm
Points
45
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$ cung. Mỗi cung $(u, v, w)$ có trọng số $w$ (có thể âm, bằng $0$ hoặc dương). Hãy tìm độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $N$:
- Nếu có chu trình âm mà từ đỉnh $1$ có thể đi tới được (tức đường đi từ $1$ đến một đỉnh thuộc chu trình âm tồn tại), in ra
-INF. - Nếu không thể đi từ $1$ đến $N$, in ra
NO_PATH. - Ngược lại, in ra độ dài đường đi ngắn nhất từ $1$ đến $N$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, 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 kết quả theo yêu cầu đề bài.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 5 2 3 -3 3 4 2 1 4 10 |
4 |
| 3 3 1 2 1 2 3 -2 3 2 -2 |
-INF |
Giới hạn
$1 \le N \le 1000$, $0 \le M \le 5000$, $|w| \le 10^9$.
Community Discussion