Đường Đi Ngắn Nhất Qua Cổng
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một thành phố có N ngã tư và M con đường một chiều. Mỗi con đường nối từ ngã tư u đến ngã tư v với chi phí w (w ≥ 0). Tuy nhiên, một số con đường có chi phí bằng 0 (đường miễn phí) và một số có chi phí bằng 1 (đường thu phí).
Hãy tìm đường đi từ ngã tư 1 đến ngã tư N với tổng chi phí nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên N M (2 ≤ N ≤ 100000, 1 ≤ M ≤ 200000).
M dòng tiếp theo, mỗi dòng chứa ba số nguyên u v w (1 ≤ u, v ≤ N, w ∈ {0, 1}) mô tả một con đường một chiều từ u đến v với chi phí w.
Dữ liệu ra
In ra một số nguyên duy nhất là chi phí nhỏ nhất để đi từ ngã tư 1 đến ngã tư N. Nếu không có đường đi, in -1.
Ví dụ
| Input | Output |
|---|---|
| 4 5\n1 2 0\n2 4 1\n1 3 1\n3 4 0\n2 3 0 | 0 |
Giới hạn
- 2 ≤ N ≤ 100000
- 1 ≤ M ≤ 200000
- w ∈ {0, 1}
Community Discussion