Chi Phí Vận Chuyển Tối Thiểu
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một mạng lưới giao thông gồm N thành phố và M tuyến đường một chiều. Mỗi tuyến đường từ u đến v có sức chứa c và chi phí vận chuyển mỗi đơn vị hàng hóa là w. Cần vận chuyển F đơn vị hàng hóa từ thành phố 1 đến thành phố N. Hãy tìm chi phí vận chuyển tối thiểu. Nếu không thể vận chuyển đủ F đơn vị, in -1.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên N M F (2 ≤ N ≤ 500, 1 ≤ M ≤ 5000, 1 ≤ F ≤ 10^9).
M dòng tiếp theo, mỗi dòng chứa bốn số nguyên u v c w (1 ≤ u, v ≤ N, 1 ≤ c ≤ 10^6, 0 ≤ w ≤ 1000) mô tả tuyến đường.
Dữ liệu ra
In ra chi phí vận chuyển tối thiểu, hoặc -1 nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 4 5 10\n1 2 5 1\n1 3 8 2\n2 4 5 3\n3 4 8 1\n2 3 3 1 | 27 |
Giới hạn
- 2 ≤ N ≤ 500
- 1 ≤ M ≤ 5000
- 1 ≤ F ≤ 10^9
- 1 ≤ c ≤ 10^6
- 0 ≤ w ≤ 1000
Community Discussion