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 os
import sys
from collections import defaultdict

import heapq

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

"""
最小費用流
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B&lang=jp
"""


class MinCostFlow:
    """
    最小費用流 ダイクストラ版
    Primal Dual
    """

    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, cost, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, cost, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap, cost in graph[v]:
                rev = [v, 0, -cost]
                edge = [u, cap, cost, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def solve(self, from_v, to_v, flow):
        """
        :param int from_v:
        :param int to_v:
        :param int flow:
        :rtype: int
        """
        res = 0
        h = [0] * len(self.graph)
        prevv = [-1] * len(self.graph)
        preve = [-1] * len(self.graph)
        remains = flow
        while remains > 0:
            dist = [float('inf')] * len(self.graph)
            dist[from_v] = 0
            heap = [(0, from_v)]

            # Dijkstra
            while heap:
                d, v = heapq.heappop(heap)
                if d > dist[v]:
                    continue
                for edge in self.graph[v]:
                    u, cap, cost, rev = edge
                    if cap > 0 and dist[v] + cost + h[v] - h[u] < dist[u]:
                        dist[u] = dist[v] + cost + h[v] - h[u]
                        prevv[u] = v
                        preve[u] = edge
                        heapq.heappush(heap, (dist[u], u))

            if dist[to_v] == float('inf'):
                # これ以上流せない
                return -1

            for i, d in enumerate(dist):
                h[i] += d

            # 最短路に流せる量
            flow = remains
            v = to_v
            while v != from_v:
                cap = preve[v][1]
                flow = min(cap, flow)
                v = prevv[v]

            # 最短路に flow だけ流す
            v = to_v
            while v != from_v:
                preve[v][1] -= flow
                preve[v][3][1] += flow
                v = prevv[v]

            remains -= flow
            res += flow * h[to_v]
        return res


V, E, F = list(map(int, sys.stdin.readline().split()))
UVCD = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

graph = [[] for _ in range(V)]
for u, v, c, d in UVCD:
    graph[u].append((v, c, d))

ans = MinCostFlow(graph=graph).solve(from_v=0, to_v=V - 1, flow=F)
print(ans)