Đường bay giảm giá

Buổi 67-68 — Mock IOI
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved