Chi Phí Vận Chuyển Tối Thiểu

Buổi 41 — SPFA & Bellman-Ford Buổi 47 — Luồng cực đại (Dinic) Buổi 52 — Mock Contest Phase 2
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved