Chuỗi Cung Ứng Linh Kiện Qua Hai Bậc
Đề bài
Một tập đoàn điện tử có $A$ xưởng đúc khuôn, $B$ trạm kiểm định trung gian và $C$ nhà máy đóng gói. Xưởng đúc thứ $i$ sản xuất tối đa $s_i$ lô linh kiện. Trạm kiểm định thứ $j$ chỉ xử lý được tối đa $m_j$ lô linh kiện và tốn phí kiểm định $f_j$ trên mỗi lô. Nhà máy đóng gói thứ $k$ cần nhận tối đa $d_k$ lô linh kiện. Ngoài ra có $E_1$ tuyến vận chuyển từ xưởng đúc sang trạm kiểm định và $E_2$ tuyến từ trạm kiểm định sang nhà máy đóng gói. Biết tập đoàn bắt buộc phải xuất xưởng đúng $K$ lô linh kiện hoàn chỉnh, hãy tìm tổng chi phí (vận chuyển + kiểm định) nhỏ nhất.
Dữ liệu vào
Dòng 1 gồm $A, B, C, K$ ($1 \le A, B, C \le 20, 1 \le K \le 500$). Dòng 2 gồm $A$ số nguyên $s_i$. Dòng 3 gồm $B$ số nguyên $m_j$. Dòng 4 gồm $B$ số nguyên $f_j$. Dòng 5 gồm $C$ số nguyên $d_k$. Dòng 6 gồm $E_1, E_2$. $E_1$ dòng tiếp theo mỗi dòng gồm $u, v, cap, cost$ (xưởng $u$ tới trạm $v$). $E_2$ dòng tiếp theo mỗi dòng gồm $v, w, cap, cost$ (trạm $v$ tới nhà máy $w$).
Dữ liệu ra
In ra tổng chi phí nhỏ nhất để cung ứng đủ $K$ lô linh kiện, hoặc -1 nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 2 2 2 4 3 3 3 3 2 1 3 3 3 3 1 1 3 2 1 2 2 4 2 2 3 1 1 1 2 3 2 1 2 2 2 2 3 1 |
16 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion