Điều Phối Năng Lượng Vệ Tinh
Đề bài
Một trạm không gian cần truyền đúng $K$ đơn vị năng lượng mặt trời từ tấm thu trung tâm (đỉnh $1$) tới kho lưu trữ chính (đỉnh $N$) qua hệ thống $M$ cáp dẫn một chiều. Mỗi cáp dẫn thứ $i$ nối từ nút $u_i$ sang $v_i$ chỉ chịu được tối đa $c_i$ đơn vị năng lượng và gây hao phí nhiệt $w_i$ cho mỗi đơn vị truyền qua. Hãy xác định tổng độ hao phí nhiệt nhỏ nhất để truyền đủ $K$ đơn vị năng lượng tới đỉnh $N$, hoặc in -1 nếu hệ thống không đủ công suất.
Dữ liệu vào
Dòng đầu gồm 4 số nguyên $N, M, K$ ($2 \le N \le 60, 1 \le M \le 200, 1 \le K \le 1000$). $M$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $u, v, c, w$ ($1 \le u, v \le N, 1 \le c \le 100, 1 \le w \le 1000$).
Dữ liệu ra
In ra một số nguyên duy nhất là tổng hao phí nhiệt tối thiểu, hoặc -1 nếu không thể truyền đủ $K$ đơn vị.
Ví dụ
| Input | Output |
|---|---|
| 4 5 4 1 2 3 2 1 3 2 5 2 3 2 1 2 4 2 4 3 4 3 2 |
23 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion