Nâng cấp đường truyền
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Hệ thống mạng gồm $N$ máy chủ và $M$ đường truyền có hướng. Mỗi đường truyền $(u, v)$ ban đầu có băng thông $c_1$ với chi phí truyền $w_1$ cho mỗi đơn vị dữ liệu. Ngoài ra, có thể mở rộng thêm tối đa $c_2$ đơn vị băng thông dự phòng trên đường này với chi phí $w_2$ ($w_2 \ge w_1$) cho mỗi đơn vị dữ liệu.
Hãy tìm chi phí nhỏ nhất để truyền $K$ đơn vị dữ liệu từ máy chủ $1$ đến máy chủ $N$, hoặc in ra -1 nếu không đủ băng thông.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 250, 1 \le M \le 2000, 1 \le K \le 10^4$).
- $M$ dòng tiếp theo, mỗi dòng chứa sáu số nguyên $u, v, c_1, w_1, c_2, w_2$ ($0 \le w_1 \le w_2 \le 10^4$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 3 2 5 1 2 2 1 5 4 2 3 3 2 4 3 |
26 |
Giới hạn
- $2 \le N \le 250, 1 \le M \le 2000$.
- Thời gian chạy: 2 giây.
Community Discussion