Đường Phố Một Chiều Và Hai Chiều

Buổi 41 — SPFA & Bellman-Ford
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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}
Draft saved