Minimum cost flow

Write codeHard45 min

Your task

You are given a directed flow network on n nodes as edges [u, v, cap, cost] (capacity and per-unit cost are non-negative integers), a source s, a target t, and an integer K. Find the minimum total cost to send EXACTLY K units of flow from s to t, where each unit traversing an edge pays that edge's cost. Return the minimum cost, or -1 if it is impossible to route K units. Constraints: up to 50 nodes; small capacities and K (each <= a few hundred).

Examples

min_cost_flow(n: int, edges: list[list[int]], s: int, t: int, K: int) -> int

Example 1

Inputmin_cost_flow(4, [[0, 1, 2, 1], [0, 2, 2, 2], [1, 3, 2, 1], [2, 3, 2, 1]], 0, 3, 3)

Output7