Hành Trình Vé Miễn Phí
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị vô hướng có trọng số gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cạnh. Cạnh thứ $i$ nối hai đỉnh $u_i, v_i$ với chi phí đi lại là $w_i$.
Bạn đang ở đỉnh $1$ và muốn đi đến đỉnh $N$. Bạn có tối đa $K$ vé miễn phí; mỗi vé cho phép bạn đi qua một cạnh bất kỳ với chi phí $0$.
Hãy tìm tổng chi phí nhỏ nhất để đi từ đỉnh $1$ đến đỉnh $N$. Nếu không thể đi đến $N$, in ra -1.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên $N, M, K$ ($1 \le N \le 5 \cdot 10^4$, $0 \le M \le 10^5$, $0 \le K \le 5$).
- $M$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N$, $1 \le w_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất, hoặc
-1nếu không có đường đi.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 1 2 10 2 4 5 1 3 3 3 4 20 |
3 |
Giới hạn
- $1 \le N \le 5 \cdot 10^4$, $0 \le M \le 10^5$, $0 \le K \le 5$
- $1 \le w_i \le 10^9$
Community Discussion