Vận Chuyển Hàng Hóa Chi Phí Thấp Nhất
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Một mạng giao thông có hướng gồm $N$ trạm (đánh số từ $1$ đến $N$) và $M$ tuyến đường. Tuyến đường thứ $i$ đi từ $u_i$ đến $v_i$, cho phép vận chuyển tối đa $c_i$ kiện hàng với chi phí $w_i$ cho mỗi kiện hàng.
Bạn cần vận chuyển đúng $K$ kiện hàng từ trạm $1$ đến trạm $N$. Hãy tìm tổng chi phí vận chuyển nhỏ nhất có thể. Nếu không thể vận chuyển đủ $K$ kiện hàng, hãy 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$, $0 \le M \le 2000$, $1 \le K \le 10^6$).
- $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u_i, v_i, c_i, w_i$ ($1 \le u_i, v_i \le N$, $1 \le c_i \le 10^6$, $0 \le w_i \le 10^6$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc
-1nếu không thể vận chuyển đủ $K$ kiện hàng.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 1 2 2 1 1 3 3 2 2 3 1 1 2 4 2 4 3 4 3 1 |
14 |
Giới hạn
- $2 \le N \le 200$, $0 \le M \le 2000$
- $1 \le K, c_i \le 10^6$, $0 \le w_i \le 10^6$
Community Discussion