Đường dây miễn phí

Binary-search Buổi 13 — Chặt nhị phân đáp án
Points
68
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Mạng viễn thông gồm $N$ trạm đánh số từ $1$ đến $N$ và $M$ tuyến cáp hai chiều, tuyến thứ $i$ nối $u_i$ với $v_i$ và có chi phí thuê là $w_i$. Bạn cần thiết lập một đường truyền từ trạm $1$ đến trạm $N$.

Nhà mạng cho phép bạn chọn tối đa $K$ tuyến cáp trên đường truyền đó để được miễn phí hoàn toàn. Với các tuyến cáp còn lại trên đường đi, bạn chỉ cần trả một mức phí bằng chi phí lớn nhất trong số chúng (nếu tất cả tuyến cáp trên đường đi đều được miễn phí, tổng chi phí là $0$).

Hãy tìm tổng chi phí nhỏ nhất có thể để truyền tin từ $1$ đến $N$. Nếu không thể đi từ $1$ đến $N$, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$.
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$.
Dữ liệu ra

In ra chi phí nhỏ nhất tìm được, hoặc -1 nếu không tồn tại đường đi.

Ví dụ
Input Output
5 7 1

1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 | 4 | | 3 1 0 1 2 10 | -1 |

Giới hạn
  • $1 \le N \le 1000$
  • $0 \le M \le 10^4$
  • $0 \le K < N$
  • $1 \le w_i \le 10^9$.
Draft saved