Đường đi ngắn nhất trên DAG có trọng số âm
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh, $M$ cạnh có trọng số (trọng số có thể âm, bằng $0$ hoặc dương) và một đỉnh xuất phát $S$.
Hãy tìm độ dài đường đi ngắn nhất từ $S$ đến tất cả các đỉnh từ $1$ đến $N$.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, S$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $1 \le S \le N$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số $u, v, w$ ($1 \le u, v \le N$, $-10^9 \le w \le 10^9$).
Dữ liệu ra
In ra $N$ giá trị cách nhau bởi dấu cách là khoảng cách ngắn nhất từ $S$ đến các đỉnh $1..N$ (in INF nếu không đi tới được).
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 1 2 5 1 3 2 3 2 -4 2 4 3 |
0 -2 2 1 |
| 4 2 2 1 2 3 3 4 -2 |
INF 0 INF INF |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $|w| \le 10^9$. Dữ liệu đảm bảo đồ thị là DAG.
Community Discussion