Tưới tiêu khu vườn
Points
70
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Hệ thống ống dẫn nước gồm $N$ nút và $M$ ống dẫn có hướng. Ống dẫn thứ $i$ nối từ $u$ đến $v$ có sức chứa tối đa $cap_i$ và hệ số ma sát $a_i$. Nếu truyền $f$ đơn vị nước ($0 \le f \le cap_i$) qua ống này, năng lượng tiêu tốn là $a_i \cdot f^2$.
Hãy tìm tổng năng lượng nhỏ nhất để dẫn $K$ đơn vị nước từ nút $1$ đến nút $N$, hoặc in ra -1 nếu không thể.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 100, 1 \le M \le 500, 1 \le K \le 100$).
- $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $u, v, cap_i, a_i$ ($1 \le cap_i \le 10, 0 \le a_i \le 100$).
Dữ liệu ra
- In ra tổng năng lượng nhỏ nhất, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 3 3 3 1 2 3 1 1 3 2 2 2 3 3 1 |
10 |
Giới hạn
- $2 \le N \le 100, 1 \le M \le 500, \sum cap_i \le 4000$.
- Thời gian chạy: 3 giây.
Community Discussion