Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Minimum Cost Flow

  Find the minimum cost to send a certain amount of flow through a flow network.

  The flow network is a directed graph where each edge $e$ has capacity $c(e)$ and cost $d(e)$. Each edge $e$ can send an amount of flow $f(e)$ where $f(e) \leq c(e)$. Find the minimum value of $\sum_{e} (f(e) \times d(e))$ to send an amount of flow $F$ from source $s$ to sink $t$.

Input

A flow network $G(V,E)$ is given in the following format.

$|V|\;|E|\;F$

$u_0\;v_0\;c_0\;d_0$

$u_1\;v_1\;c_1\;d_1$

:

$u_{|E|1}\;v_{|E|-1}\;c_{|E|-1}\;d_{|E|-1}$

  $|V|$, $|E|$, $F$ are the number of vertices, the number of edges, and the amount of flow of the flow network respectively. The vertices in $G$ are named with the numbers $0, 1,..., |V|−1$. The source is $0$ and the sink is $|V|−1$.

$u_i$, $v_i$, $c_i$, $d_i$ represent $i$-th edge of the flow network. A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$, and $c_i$ and $d_i$ are the capacity and the cost of $i$-th edge respectively.

Output

  Print the minimum value in a line. If it is impossible to send the flow from the source $s$ to the sink $t$, print -1.

Constraints

 2 ≤ $|V|$ ≤ 100
	

 1 ≤ $|E|$ ≤ 1000

 0 ≤ $F$ ≤ 1000
		

 0 ≤ $c_i$, $d_i$ ≤ 1000
	

 $u_i$ $\ne$ $v_i$

 If there is an edge from vertex $x$ to vertex $y$, there is no edge from vertex $y$ to vertex $x$.

Sample Input

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

Sample Output

6



Sample input:
4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
from heapq import *

# G : [to/from, cap, cost, rev]
def minimumCostFlow(N: int, G: list, s: int, t: int, flow: int):
	ret = 0
	INF = 1 << 60
	potential = [0] * N
	pre_vtx = [None] * N
	pre_edge = [None] * N

	while flow > 0:
		dist = [INF] * N
		dist[s] = 0
		visited = [False] * N
		q = [(0, s)]
		while q:
			d, cur = heappop(q)
			if visited[cur]:
				continue
			visited[cur] = True
			for i in range(len(G[cur])):
				e = G[cur][i]
				nxt = e[0]
				if e[1] > 0 and dist[nxt] > dist[cur] + e[2] + potential[cur] - potential[nxt]:
					dist[nxt] = dist[cur] + e[2] + potential[cur] - potential[nxt]
					pre_vtx[nxt] = cur
					pre_edge[nxt] = i
					heappush(q, (dist[nxt], nxt))
		if dist[t] == INF:
			return -1
		for i in range(N):
			potential[i] += dist[i]
		df = flow
		now = t
		while now != s:
			df = min(df, G[pre_vtx[now]][pre_edge[now]][1])
			now = pre_vtx[now]
		flow -= df
		ret += df * potential[t]
		now = t
		while now != s:
			G[pre_vtx[now]][pre_edge[now]][1] -= df
			G[now][G[pre_vtx[now]][pre_edge[now]][3]][1] += df
			now = pre_vtx[now]
	return ret


import sys
input = sys.stdin.buffer.readline


def main():
	N, M, F = map(int, input().split())
	G = [[] for _ in range(N)]  # [to/from, cap, cost, rev]
	for _ in range(M):
		u, v, c, d = map(int, input().split())
		G[u].append([v, c, d, len(G[v])])
		G[v].append([u, 0, -d, len(G[u]) - 1])
	print(minimumCostFlow(N, G, 0, N - 1, F))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import heapq as hp
class MinimumCostFlow():
    def __init__(self, N, INF=10**18):
        self.graph = [{} for _ in range(N)]
        self.N = N
        self.INF = INF
    
    def add_edge(self, u, v, cap, cost, undirected=False):
        # u -> v (maxflow, cost)
        if cap == 0: return
        if undirected:
            self.graph[u][v] = [cap, cost]
            self.graph[v][u] = [cap, -cost]
        elif v in self.graph[u]:
            self.graph[u][v] = [cap, cost]
        else:
            self.graph[u][v] = [cap, cost]
            self.graph[v][u] = [0, -cost]       
    
    def dijkstra(self, start):
        self.dist = [self.INF]*self.N # nearest distance
        self.dist[start] = 0
        self.que = [(0, start)]
        while self.que:
            d, v = hp.heappop(self.que)
            if self.dist[v] < d: continue
            for nv, (ncap, ncost) in self.graph[v].items():
                if ncap > 0 and self.dist[nv] > self.dist[v] + ncost + self.H[v] - self.H[nv]:
                    self.dist[nv] = self.dist[v] + ncost + self.H[v] - self.H[nv]
                    self.prevv[nv] = v
                    hp.heappush(self.que, (self.dist[nv], nv))
                
    
    def min_cost_flow(self, start, finish, flow):
        self.res = 0
        self.prevv = [-1]*self.N
        self.H = [0]*self.N # potential
        while flow > 0:
            self.dijkstra(start)
            if self.dist[finish] == self.INF: return -1 # cant run flow anymore
            for i in range(self.N):
                self.H[i] += self.dist[i]
            
            d = flow
            v = finish
            while v != start:
                d = min(d, self.graph[self.prevv[v]][v][0])
                v = self.prevv[v]
            flow -= d
            self.res += d*self.H[finish]

            v = finish
            while v != start:
                self.graph[self.prevv[v]][v][0] -= d
                self.graph[v][self.prevv[v]][0] += d
                v = self.prevv[v]
        return self.res
    

if __name__ == "__main__":
    import sys
    input = sys.stdin.readline

    V, E, F = map(int, input().split())
    fl = MinimumCostFlow(V)
    for _ in range(E):
        u, v, c, d = map(int, input().split())
        fl.add_edge(u, v, c, d)
    
    print(fl.min_cost_flow(0, V-1, F))

Submission status: Accepted

Solution code:
V,E,F=map(int,input().split())
EDGE=dict()
EDGE2=[[] for i in range(V)]

for i in range(E):
    x,to,c,d=map(int,input().split())
    EDGE[(x,to)]=[c,d]
    EDGE2[x].append(to)

BACK=[-1]*V
P=[0]*V

# 一回ベルマンフォードをしてポテンシャルを求める.

ANS=[float("inf")]*V
ANS[0]=0

for rep in range(V):    
    for x,to in EDGE:
        c,d=EDGE[(x,to)]
        if c>0 and ANS[to]>ANS[x]+d:
            ANS[to]=ANS[x]+d
            BACK[to]=x

P=[ANS[i] for i in range(V)]
LA=ANS[V-1]

NOW=V-1
while NOW!=0:
    fr=BACK[NOW]
    EDGE[(fr,NOW)][0]-=1

    if (NOW,fr) in EDGE:
        EDGE[(NOW,fr)][0]+=1
    else:
        EDGE[(NOW,fr)]=[1,-EDGE[fr,NOW][1]]
        EDGE2[NOW].append(fr)

    NOW=fr
    
for x,to in EDGE:
    EDGE[(x,to)][1]+=P[x]-P[to]

# あとはダイクストラを使える.

import heapq

for i in range(F-1):
    ANS=[float("inf")]*V
    Q=[(0,0)]
    ANS[0]=0

    while Q:
        time,ind=heapq.heappop(Q)
        if time>ANS[ind]:
            continue

        for to in EDGE2[ind]:
            c,d=EDGE[(ind,to)]
            if c>0 and ANS[to]>ANS[ind]+d:
                ANS[to]=ANS[ind]+d
                BACK[to]=ind
                heapq.heappush(Q,(ANS[to],to))

    LA+=ANS[V-1]+P[V-1]-P[0]

    if LA==float("inf"):
        break

    P=[P[i]-ANS[i] for i in range(V)]

    NOW=V-1
    while NOW!=0:
        fr=BACK[NOW]
        EDGE[(fr,NOW)][0]-=1

        if (NOW,fr) in EDGE:
            EDGE[(NOW,fr)][0]+=1
        else:
            EDGE[(NOW,fr)]=[1,-EDGE[fr,NOW][1]]
            EDGE2[NOW].append(fr)

        NOW=fr

    for x,to in EDGE:
        EDGE[(x,to)][1]+=ANS[to]-ANS[x]
    

if LA==float("inf"):
    print(-1)
else:
    print(LA)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
class MinCostFlowwithDijkstra:
    INF = 1<<31
    
    def __init__(self, N):
        self.N = N
        self.Edge = [[] for _ in range(N)]
    
    def add_edge(self, st, en, cap, cost):
        self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
        self.Edge[en].append([st, 0, -cost, len(self.Edge[st])-1])
    
    def get_mf(self, so, si, fl):
        N = self.N
        INF = self.INF
        res = 0
        Pot = [0]*N
        geta = N
        
        
        prv = [None]*N
        prenum = [None]*N
        while fl:
            dist = [INF]*N
            dist[so] = 0
            Q = [so]
            
            while Q:
                cost, vn = divmod(hpp(Q), geta)
                if dist[vn] < cost:
                    continue
                
                for enum in range(len(self.Edge[vn])):
                    vf, cap, cost, _ = self.Edge[vn][enum]
                    cc = dist[vn] + cost - Pot[vn] + Pot[vf]
                    if cap > 0 and dist[vf] > cc:
                        dist[vf] = cc
                        prv[vf] = vn
                        prenum[vf] = enum
                        hp(Q, cc*geta + vf)
            
            if dist[si] == INF:
                return -1
            
            for i in range(N):
                Pot[i] -= dist[i]
            
            cfl = fl
            vf = si
            while vf != so:
                cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
                vf = prv[vf]
            
            fl -= cfl
            res -= cfl*Pot[si]
            vf = si
            while vf != so:
                e = self.Edge[prv[vf]][prenum[vf]]
                e[1] -= cfl
                self.Edge[vf][e[3]][1] += cfl
                vf = prv[vf]
        return res

N, M, F = map(int, readline().split())
T = MinCostFlowwithDijkstra(N)
for _ in range(M):
    u, v, cap, cost = map(int, readline().split())
    T.add_edge(u, v, cap, cost)

print(T.get_mf(0, N-1, F))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

V,E,F = map(int,sys.stdin.readline().split())
uvcd = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param

#uvcd = [[0,1,1,1],[0,2,3,2],[1,2,1,2],[2,3,2,1]]
capacityG = {i:{} for i in range(V)} #capacity
costG = {i:{} for i in range(V)} #capacity

for u,v,c,d in uvcd:
    capacityG[u][v] = c
    costG[u][v] = d
    if not u in capacityG[v]:
        capacityG[v][u] = 0
        costG[v][u] = -d

def shortest_path(V,costG,capacityG,start=0):
    distances = [INF]*V
    distances[start] = 0
    parents = list(range(V))

    for _ in range(V):
        modified = False
        for src in range(V):
            if distances[src] == INF: continue
            for dst,cost in costG[src].items():
                if capacityG[src][dst] > 0 and distances[dst] > distances[src] + cost:
                    distances[dst] = distances[src] + cost
                    parents[dst] = src
                    modified = True
        if modified == False:
            return distances,parents
    return None,None

rest = F
total_cost = 0
while rest != 0:
    distances,p = shortest_path(V,costG,capacityG,0)
    if not distances or distances[V-1] == INF:
        print(-1)
        exit()
    cur = V-1
    flow = rest
    while cur != 0:
        flow = min(flow,capacityG[p[cur]][cur])
        cur = p[cur]
    rest -= flow
    total_cost += distances[V-1]*flow
    cur = V-1
    while cur != 0:
        capacityG[p[cur]][cur] -= flow
        capacityG[cur][p[cur]] += flow #rev
        cur = p[cur]
print(total_cost)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]


    def add_edge(self, fr, to, cap, cost):
        G = self.g
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.n
        G = self.g
        INF = 10**18

        prevv = [0]*N
        preve = [0]*N

        res = 0
        while f > 0:
            dist = [INF]*N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF: continue
                    for i in range(len(G[v])):
                        to, cap, cost, rev = G[v][i]
                        if cap > 0 and dist[to] > dist[v]+cost:
                            dist[to] = dist[v]+cost
                            prevv[to] = v
                            preve[to] = i
                            update = True

            if dist[t] == INF:
                return -1

            d = f
            v = t
            while v != s:
                d = min(d, G[prevv[v]][preve[v]][1])
                v = prevv[v]
            f -= d
            res += d*dist[t]

            v = t
            while v != s:
                e = G[prevv[v]][preve[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prevv[v]

        return res
            

V, E, F = MAP()
mcf = MinCostFlow(V)
for _ in range(E):
    u, v, c, d = MAP()
    mcf.add_edge(u, v, c, d)
print(mcf.flow(0, V-1, F))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import heapq

class MinCostFlow:
    class Edge:
        def __init__(self,to,cap,rev,cost):
            self.to = to
            self.cap = cap
            self.rev = rev
            self.cost = cost

    def __init__(self,n,inf=1000000007):
        self.n = n
        self.inf = inf
        self.e = [[] for _ in range(n)]

    def add_edge(self, fr, to, cap, cost):
        self.e[fr].append(self.Edge(to,cap,len(self.e[to]),cost))
        self.e[to].append(self.Edge(fr,0,len(self.e[fr])-1,-cost))

    def compute(self,source,sink,f):
        res = 0
        h = [0]*self.n
        prevv = [0]*self.n
        preve = [0]*self.n
        while (f > 0):
            pq = []
            dist = [self.inf]*self.n
            dist[source] = 0
            heapq.heappush(pq,(0,source))
            while pq:
                cost, v = heapq.heappop(pq)
                cost = -cost
                if dist[v] < cost:continue
                for i, edge in enumerate(self.e[v]):
                    if edge.cap > 0 and dist[v] - h[edge.to] < dist[edge.to] - edge.cost - h[v]:
                        dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to]
                        prevv[edge.to] = v
                        preve[edge.to] = i
                        heapq.heappush(pq,(-dist[edge.to],edge.to))
            if dist[sink] == self.inf:return -1
            for v in range(self.n):
                h[v] += dist[v]

            d, v = f, sink
            while v != source:
                d = min(d,self.e[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d*h[sink]
            v = sink
            while v != source:
                self.e[prevv[v]][preve[v]].cap -= d
                self.e[v][self.e[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]
        return res


def main():
    v,e,f = map(int,input().split())
    MCF = MinCostFlow(v)
    for _ in range(e):
        a,b,c,d = map(int,input().split())
        MCF.add_edge(a,b,c,d)
    print(MCF.compute(0,v-1,f))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ノードをtupleで渡す
from collections import defaultdict
from heapq import *
class MinCostFlow:
    def __init__(self):
        self.inf=10**9
        self.to = defaultdict(dict)

    def add_edge(self, u, v, cap, cost):
        self.to[u][v]=[cap, cost]
        self.to[v][u]=[0, -cost]

    # s...source,t...sink,f...flow
    # これが本体
    def cal(self,s,t,f):
        min_cost=0
        pot=defaultdict(int)
        while f:
            dist = {}
            pre_u={}   # 最短距離の遷移元の頂点
            # ダイクストラで最短距離を求める
            hp=[]
            heappush(hp,(0,s))
            dist[s]=0
            while hp:
                d,u=heappop(hp)
                if d>dist[u]:continue
                for v,[cap,cost] in self.to[u].items():
                    if cap==0:continue
                    nd=dist[u]+cost+pot[u]-pot[v]
                    dist.setdefault(v, self.inf)
                    if nd>=dist[v]:continue
                    dist[v]=nd
                    pre_u[v]=u
                    heappush(hp,(nd,v))
            # sinkまで届かなかったら不可能ということ
            if t not in dist:return -1
            # ポテンシャルを更新する
            for u,d in dist.items():pot[u]+=d
            # パスs-t上で最小の容量=流す量を求める
            u=t
            min_cap=f
            while u!=s:
                u,v=pre_u[u],u
                min_cap=min(min_cap,self.to[u][v][0])
            # フローから流す量を減らし、コストを加える
            f-=min_cap
            min_cost+=min_cap*pot[t]
            # パスs-tの容量を更新する
            u=t
            while u!=s:
                u,v=pre_u[u],u
                self.to[u][v][0]-=min_cap
                self.to[v][u][0]+=min_cap
        return min_cost

def main():
    n,m,f=map(int,input().split())
    mc=MinCostFlow()
    for _ in range(m):
        u,v,c,d=map(int,input().split())
        mc.add_edge(u,v,c,d)
    print(mc.cal(0,n-1,f))

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1 << 100
    NN = N
    LN = NN.bit_length()
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    while f > 0:
        h = [0] * NN
        dist = [INF] * NN
        dist[s] = 0
        Q = []
        heappush(Q, s)
        while len(Q):
            x = heappop(Q)
            d, v = (x>>LN), x % (1<<LN)
            if dist[v] < d: continue
            for i, (w, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[w] > dist[v] + c + h[v] - h[w]:
                    dist[w] = dist[v] + c + h[v] - h[w]
                    prevv[w] = v
                    preve[w] = i
                    heappush(Q, (dist[w] << LN) + w)
        if dist[t] == INF:
            return -1
        for v in range(N):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

N, M, F = map(int, input().split())
E = []
for i in range(M):
    u, v, c, d = map(int, input().split())
    E.append((u, v, c, d))

print(min_cost_flow_dijkstra(E, 0, N-1, F))

Submission status: Accepted

Solution code:
from typing import List, Iterator, Optional, Tuple


def trace_back(sink: int,
               predecessors: List[Optional[Tuple[int, int]]]) -> Iterator[List[int]]:
    p = predecessors[sink]
    while p is not None:
        v, i = p
        yield edges[v][i]
        p = predecessors[v]


def min_cost_flow(source: int, sink: int, required_flow: int) -> int:
    res = 0
    while required_flow:
        dist = [float('inf')] * n
        dist[source] = 0
        predecessors: List[Optional[Tuple[int, int]]] = [None] * n

        while True:
            updated = False
            for v in range(n):
                if dist[v] == float('inf'):
                    continue
                for i, (remain, target, cost, _) in enumerate(edges[v]):
                    new_dist = dist[v] + cost
                    if remain and dist[target] > new_dist:
                        dist[target] = new_dist
                        predecessors[target] = (v, i)
                        updated = True
            if not updated:
                break

        if dist[sink] == float('inf'):
            return -1

        aug = min(required_flow, min(e[0] for e in trace_back(sink, predecessors)))
        required_flow -= aug
        res += int(aug * dist[sink])
        for e in trace_back(sink, predecessors):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


if __name__ == "__main__":
    n, m, f = map(int, input().split())
    edges = [[] for _ in range(n)]  # type: ignore

    for _ in range(m):
        s, t, c, d = map(int, input().split())
        es, et = edges[s], edges[t]
        ls, lt = len(es), len(et)
        es.append([c, t, d, lt])
        et.append([0, s, -d, ls])

    print(min_cost_flow(0, n - 1, f))

Submission status: Accepted

Solution code:
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)