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

INF = 10 ** 5


class MinCostFlow:
    """
    最小費用流の ダイクストラ版
    蟻本 P.203
    """

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]
        # 最小コスト見つかったあとに, route を取得するために使用
        self.prevv = [INF] * V
        self.preve = [INF] * V

        self.h = [0] * V  # ポテンシャル

    def add_edge(self, from_, to_, cap, cost):
        """
        from から to へ向かう容量 cap, コスト cost の辺をグラフに追加
        """
        self.G[from_].append([to_, cap, cost, len(self.G[to_])])
        self.G[to_].append([from_, 0, -cost, len(self.G[from_]) - 1])

    def _get_dist(self, s, t, f):
        """
        prevv,preve から 最大で流せる量を返す

        :param s: 始点
        :param t: 終点
        :param f: 最大で流したい量
        :return:
        """
        d = f
        v = t
        while v != s:
            pre_v = self.prevv[v]
            pre_edge = self.preve[v]
            d = min(d, self.G[pre_v][pre_edge][1])  # 1:cap のindex
            v = pre_v
        return d

    def _update_cap(self, s, t, d):
        """ capacity 更新 """
        v = t
        while v != s:
            pre_v = self.prevv[v]
            pre_e = self.preve[v]
            e = self.G[pre_v][pre_e]  # type:list
            e[1] -= d  # cap 更新
            rev = e[3]  # type:int
            self.G[v][rev][1] += d  # 逆辺のcap更新

            v = pre_v

    def solve(self, s, t, f):
        res = 0
        self.h = [0] * self.V
        dist = [INF] * self.V  # 最短経路
        while f > 0:
            que = []  # priority queue (<最短距離, 頂点の番号>) を要素にもつ. ダイクストラ用
            for i in range(self.V):
                dist[i] = INF
            dist[s] = 0

            heapq.heappush(que, (0, s))

            while que:

                p = heapq.heappop(que)
                v = p[1]  # 注目する頂点
                if (dist[v] < p[0]): continue

                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    to_ = e[0]
                    cap = e[1]
                    cost = e[2]

                    if cap <= 0: continue

                    # u -> v のとき, dist[v] は dist[u] + cost + h(u) -h(v) # p.202
                    if dist[to_] > dist[v] + cost + self.h[v] - self.h[to_]:
                        dist[to_] = dist[v] + cost + self.h[v] - self.h[to_]
                        self.prevv[to_] = v
                        self.preve[to_] = i
                        heapq.heappush(que, (dist[to_], to_))

            if dist[t] == INF:  # 経路なし(これ以上流せない)
                return -1

            for v in range(self.V):
                self.h[v] += dist[v]

            # 流せる量を取得
            d = self._get_dist(s, t, f)
            res += d * self.h[t]
            f -= d

            # update capacity
            self._update_cap(s, t, d)

        return res


v,e,f = [int(_) for _ in input().split()]
mcf = MinCostFlow(v)
for i in range(e):
    mcf.add_edge( *[int(_) for _ in input().split()])
print(mcf.solve(0,v-1,f))