Đường dây miễn phí
Points
68
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Đề 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$.
Community Discussion