Đường Phố Một Chiều Và Hai Chiều
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Thành phố có N giao lộ và M tuyến đường một chiều. Một số tuyến đường là cao tốc miễn phí (trọng số 0), số còn lại là đường thu phí (trọng số 1). Hãy tìm tổng chi phí nhỏ nhất để đi từ giao lộ 1 đến giao lộ 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 (với w ∈ {0, 1}) mô tả đường đi từ u đến v với chi phí w.
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất để đi từ 1 đến N, hoặc
-1nếu không thể đi đến N.
Ví dụ
| Input | Output |
|---|---|
| 5 6 1 2 1 1 3 0 3 4 0 4 2 0 2 5 1 3 5 1 |
1 |
| 4 2 1 2 0 3 4 1 |
-1 |
Giới hạn
- 1 ≤ N ≤ 50000
- 0 ≤ M ≤ 100000
- 1 ≤ u, v ≤ N
- w ∈ {0, 1}
Community Discussion