Problem: Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output

Solution (in PYTHON3):

Solution:
import heapq


class PrimalDual:
    def __init__(self, n: int):
        """頂点数をnとする。"""
        self.INF = 10 ** 9 + 7
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, _from: int, to: int, capacity: int, cost: int):
        """辺を追加
        1. _fromからtoへ向かう容量capacity、単位コストcostの辺をグラフに追加する。
        2. toから_fromへ向かう容量0、単位コスト-costの辺をグラフに追加する。
        """
        forward = [to, capacity, cost, None]
        forward[3] = backward = [_from, 0, -cost, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)

    def min_cost_flow(self, s: int, t: int, f: int) -> int:
        """s-tパス上に流量fを流すときの最小費用流を求める。
        計算量: O(|F||E|log|V|)
        """
        res = 0
        potential = [0] * self.n
        prv_v = [0] * self.n
        prv_e = [None] * self.n
        while f > 0:
            # ポテンシャルを用いたダイクストラ法
            dist = [self.INF] * self.n
            dist[s] = 0
            q = [(0, s)]  # q = [(sからのコスト, 現在地)]
            while q:
                cost, _from = heapq.heappop(q)
                if dist[_from] < cost:
                    continue
                for edge in self.graph[_from]:
                    to, capacity, cost, _ = edge
                    p_diff = potential[_from] - potential[to]
                    if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
                        dist[to] = dist[_from] + cost + p_diff
                        prv_v[to] = _from
                        prv_e[to] = edge
                        heapq.heappush(q, (dist[to], to))

            if dist[t] == self.INF:
                return -1
            for i in range(self.n):
                if dist[i] != self.INF:
                    potential[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += potential[t] * d
            v = t
            while v != s:
                edge = prv_e[v]
                edge[1] -= d
                edge[3][1] += d
                v = prv_v[v]
        return res


n, m, f = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]


pd = PrimalDual(n)
for edge in edges:
    pd.add_edge(*edge)
    
ans = pd.min_cost_flow(0, n - 1, f)
print(ans)