Hành Trình Vé Miễn Phí

Buổi 73-74 — Virtual CF Graphs
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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 -1 nế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$
Draft saved