Gửi đúng K đơn hàng
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Một công ty cần vận chuyển chính xác $K$ đơn hàng từ kho trung tâm (đỉnh $1$) đến cảng xuất khẩu (đỉnh $N$) qua mạng lưới giao thông có hướng gồm $N$ nút và $M$ tuyến đường.
Mỗi tuyến đường $(u, v)$ cho phép chở tối đa $cap$ đơn hàng với chi phí $cost$ cho mỗi đơn hàng. Hãy tìm tổng chi phí nhỏ nhất để gửi đủ $K$ đơn hàng. Nếu không thể gửi đủ $K$ đơn hàng, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 200, 1 \le M \le 2000, 0 \le K \le 10^4$).
- $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, cap, cost$ ($1 \le u, v \le N$, $1 \le cap \le 10^4$, $0 \le cost \le 10^4$).
Dữ liệu ra
- In ra một số nguyên duy nhất là chi phí nhỏ nhất, hoặc
-1nếu không thể gửi đủ $K$ đơn hàng.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 1 2 3 2 1 3 2 4 2 3 1 1 2 4 2 5 3 4 3 1 |
21 |
Giới hạn
- $2 \le N \le 200, 1 \le M \le 2000, 0 \le K \le 10^4$.
- Thời gian chạy: 2 giây.
Community Discussion