Phiếu Giảm Giá Đường Cao Tốc

Buổi 19 — Đường đi ngắn nhất
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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$
Draft saved