Đường bay giảm giá
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
An cần di chuyển từ thành phố $1$ đến thành phố $N$ qua một mạng lưới gồm $M$ chuyến bay một chiều. Mỗi chuyến bay từ thành phố $u$ đến $v$ có chi phí là $w$.
An sở hữu tối đa $K$ phiếu giảm giá. Khi sử dụng một phiếu giảm giá trên một chuyến bay có chi phí $w$, chi phí của chuyến bay đó giảm xuống còn $\lfloor w / 2 \rfloor$. Mỗi chuyến bay chỉ được áp dụng tối đa một phiếu giảm giá.
Hãy tìm tổng chi phí nhỏ nhất để An đi từ thành phố $1$ đến thành phố $N$. Nếu không thể đến được thành phố $N$, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa 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 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$, $1 \le w \le 10^9$) mô tả một chuyến bay một chiều từ $u$ đến $v$ với chi phí $w$.
Kết quả
In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc -1 nếu không có đường đi.
Subtasks
- Subtask 1 (20%): $K = 0$.
- Subtask 2 (30%): $K = 1, N \le 1000$.
- Subtask 3 (50%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 3 4 1 1 2 3 2 3 1 1 3 7 2 1 5 |
2 |
Community Discussion