Đường Đi Ngắn Nhất Qua Cổng

Buổi 41 — SPFA & Bellman-Ford Buổi 52 — Mock Contest Phase 2
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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}
Draft saved