Phiếu Giảm Giá Đường Cao Tốc
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng có trọng số không âm gồm $N$ đỉnh và $M$ cung. Bạn được tặng $K$ phiếu giảm giá. Khi đi qua một cung có trọng số $w$, bạn có thể sử dụng tối đa $1$ phiếu giảm giá để giảm trọng số cung đó xuống còn $\lfloor w / 2 \rfloor$ (mỗi phiếu chỉ dùng được một lần, không bắt buộc phải dùng hết cả $K$ phiếu). Hãy tìm chi phí nhỏ nhất để đi từ đỉnh $1$ đến đỉnh $N$ (hoặc -1 nếu không có đường đi).
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, K$ ($1 \le N \le 10^4$, $0 \le M \le 5 \times 10^4$, $0 \le K \le 10$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $0 \le w \le 10^9$).
Dữ liệu ra
- In ra chi phí nhỏ nhất từ $1$ đến $N$, hoặc
-1nếu không tồn tại đường đi.
Ví dụ
| Input | Output |
|---|---|
| 3 4 1\n1 2 3\n2 3 1\n1 3 7\n2 1 5 | 2 |
| 4 4 2\n1 2 10\n2 3 10\n3 4 10\n1 4 100 | 20 |
Giới hạn
- $1 \le N \le 10^4$
- $0 \le M \le 5 \times 10^4$
- $0 \le K \le 10$
- $0 \le w \le 10^9$
Community Discussion