Đường đi ngắn nhất với trọng số âm

Algorithms Buổi 65-66 — Mock HSG Graphs
Points
45
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$ 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$.

Draft saved