Problem:
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

Solution (Python):
import heapq

INF = 10 ** 5


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

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]
        
        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])  
            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]  
            e[1] -= d  
            rev = e[3]  
            self.G[v][rev][1] += d  

            v = pre_v

    def solve(self, s, t, f):
        res = 0
        self.h = [0] * self.V
        dist = [INF] * self.V  
        while f > 0:
            que = []  
            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

                    
                    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

            
            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))

Solution (Python):
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()

Solution (Python):

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]

    
    
    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))
            
            if t not in dist:return -1
            
            for u,d in dist.items():pot[u]+=d
            
            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]
            
            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()

Solution (Python):
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))

Solution (Python):
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)]  

    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))

Solution (Python):
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)]

            
            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]

            
            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)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007



"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
                print(dist, q)
    return dist

v,e,r = map(int, input().split(" "))
adj = [[] for i in range(v)]
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj[s].append([t, d])
lis = dijkstra(v, r)
print(lis)
for i in lis:
    print(str(i).upper())
"""


"""
def bellman_ford(num, start):
    dist = [float("inf")]*num
    dist[start] = 0
    for i in range(num):
        update = False
        for fro, to, cost in e:
            d = dist[fro] + cost
            if dist[to] > d:
                dist[to] = d
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return dist

v,E,r = map(int, input().split(" "))
e = []
for i in range(E):
    s,t,d = map(int, input().split(" "))
    e.append([s, t, d])
lis = bellman_ford(v, r)
if not lis:
    print("NEGATIVE CYCLE")
else:
    for i in lis:
        print(str(i).upper())
"""

"""
def warshallfloyd(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])
v,e = map(int, input().split())
d = [[float("inf") for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i] = 0
for i in range(e):
    s, t, c = map(int, input().split())
    d[s][t] = c
warshallfloyd(v)
for i in range(v):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        quit()
for i in d:
    for j in range(v):
        if j < v-1:
            print(str(i[j]).upper(), end = " ")
        else:
            print(str(i[j]).upper())
"""



"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
v,e = LI()
c = LIR(e)
c.sort(key = lambda x:x[2])
par = [i for i in range(v)]
rank = [0 for i in range(v)]
k = 0
ans = 0
for a,b,w in c:
    if not same(a,b):
        k += 1
        unite(a,b)
        ans += w
    if k == v-1:
        break
print(ans)
"""


"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank(x) < rank(y):
        par[x] = y
    else:
        par[y] = x
        if rank(x) == rank(y):
            rank[x] += 1
"""











"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)
"""


"""
def visit(s):
    if f[s]:
        f[s] = 0
        for t in v[s]:
            visit(t)
        l.append(s)
n,e = LI()
v = [[] for i in range(n)]
for i in range(e):
    s,t = LI()
    v[s].append(t)
l = []
f = [1 for i in range(n)]
for i in range(n):
    visit(i)
l = l[::-1]
for i in l:
    print(i)
"""



"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = II()
adj = [[] for i in range(n)]
for i in range(n-1):
    s,t,w = LI()
    adj[s].append([t, w])
    adj[t].append([s, w])
d = dijkstra(n,0)
i = d.index(max(d))
d2 = dijkstra(n,i)
print(max(d2))
"""


"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
    s, t, w = map(int, input().split(" "))
    adj[s].append([t, w])
    adj[t].append([s, w])
for i in range(n):
    s = dijkstra(n,i)
    print(max(s))
"""









"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in v[x]:
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return None,0
    path = [None]*(bfs_map[g]+1)
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in v[y]:
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return path,m

def ford_fulkerson(s,g,c,n):
    f = 0
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        f += m
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return f

n,e = LI()
c = [defaultdict(lambda : 0) for j in range(n)]
v = [[] for i in range(n)]
for i in range(e):
    a,b,w = LI()
    c[a][b] = w
    v[a].append(b)
    v[b].append(a)
print(ford_fulkerson(0,n-1,c,n))
"""

def dijkstra(s,h):
    dist = [float("inf")]*n
    prev = [-1]*n
    dist[s] = 0
    q = [(0,s)]
    while q:
        dx,x = heappop(q)
        for y in v[x]:
            if cap[x][y] <= 0:
                continue
            dy = dx+cost[x][y]+h[x]-h[y]
            if dy < dist[y]:
                dist[y] = dy
                prev[y] = x
                heappush(q,(dy,y))
    return (dist,prev)

def minimim_flow(s,g,f):
    res = 0
    h = [0]*n
    while f > 0:
        dist,prev = dijkstra(s,h)
        if dist[g] == float("inf"):
            return -1
        for i in range(n):
            h[i] += dist[i]
        flow = f
        y = g
        while y != s:
            x = prev[y]
            if cap[x][y] < flow:
                flow = cap[x][y]
            y = x
        f -= flow
        res += flow*h[g]

        y = g
        while y != s:
            x = prev[y]
            cap[x][y] -= flow
            cap[y][x] += flow
            y = x
    return res

n,m,f = LI()
v = [[] for i in range(n)]
cap = [defaultdict(lambda : 0) for i in range(n)]
cost = [defaultdict(lambda : 0) for i in range(n)]
for i in range(m):
    a,b,c,d = LI()
    v[a].append(b)
    v[b].append(a)
    cost[a][b] = d
    cost[b][a] = -d
    cap[a][b] = c
print(minimim_flow(0,n-1,f))


"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

x,y,e = LI()
c = [[0 for i in range(x+y+2)] for j in range(x+y+2)]
for i in range(x):
    c[0][i+1] = 1
for i in range(y):
    c[x+i+1][x+y+1] = 1
for i in range(e):
    a,b = LI()
    c[a+1][x+b+1] = 1
print(ford_fulkerson(0,x+y+1,c,x+y+2))
"""

Solution (Python):
from heapq import heappush, heappop
import collections


class MinCostFlowDijkstra:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)

    def add(self, fro, to, cap, cost, directed=True):
        
        if directed:
            self.edges[fro].append([to, cap, cost, len(self.edges[to])])
            self.edges[to].append([fro, 0, -cost, len(self.edges[fro]) - 1])
        else:  
            self.edges[fro].append([to, cap, cost, len(self.edges[to])])
            self.edges[to].append([fro, 0, -cost, len(self.edges[fro]) - 1])
            self.edges[to].append([fro, cap, cost, len(self.edges[fro])])
            self.edges[fro].append([to, 0, -cost, len(self.edges[to]) - 1])

    def minCostFlow(self, start, goal, flow):
        res = 0
        potential = collections.defaultdict(int)
        prevVertex = collections.defaultdict(int)
        prevEdge = collections.defaultdict(int)

        while flow > 0:
            dist = collections.defaultdict(lambda: float('inf'))
            dist[start] = 0
            que = []
            heappush(que, (0, start))

            while que:
                k, v = heappop(que)
                if dist[v] < k:
                    continue
                for i, (to, cap, cost, _) in enumerate(self.edges[v]):
                    if cap > 0 and dist[to] > dist[v] + cost + potential[v] - potential[to]:
                        dist[to] = dist[v] + cost + potential[v] - potential[to]
                        prevVertex[to] = v
                        prevEdge[to] = i
                        heappush(que, (dist[to], to))
            if dist[goal] == float('inf'):
                return -1

            for i in range(self.N):
                potential[i] += dist[i]

            d = flow
            v = goal
            while v != start:
                d = min(d, self.edges[prevVertex[v]][prevEdge[v]][1])
                v = prevVertex[v]
            flow -= d
            res += d * potential[goal]
            v = goal
            while v != start:
                e = self.edges[prevVertex[v]][prevEdge[v]]
                e[1] -= d
                self.edges[v][e[3]][1] += d
                v = prevVertex[v]
            
        return res


V, E, F = map(int, input().split())
graph = MinCostFlowDijkstra(V)
for _ in range(E):
    u, v, c, d = map(int, input().split())
    graph.add(u, v, c, d)

print(graph.minCostFlow(0, V-1, F))

Solution (Python):




WEIGHT_MAX = 10 ** 10


class Edge:
    __slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

    def __init__(self, v, w, capacity, cost=0):
        self.src = v
        self.dest = w
        self.capacity = capacity
        self.cost = cost
        self.flow = 0

    def other(self, v):
        if v == self.src:
            return self.dest
        else:
            return self.src

    def residual_capacity(self, v):
        if v == self.src:
            return self.capacity - self.flow
        else:
            return self.flow

    def cost_from(self, v):
        if v == self.src:
            return self.cost
        else:
            return -self.cost

    def add_flow(self, v, f):
        if v == self.src:
            self.flow += f
        else:
            self.flow -= f

    def __str__(self):
        return "{} {} {} {} {}".format(self.src, self.dest, self.capacity,
                                       self.cost, self.flow)


class Network:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)
        self._edges[edge.dest].append(edge)

    def adj(self, v):
        return self._edges[v]

    def flow(self, v):
        return sum(e.flow for e in self.adj(v) if e.src == v)

    def cost(self):
        cost = 0
        for v in range(self.v):
            for e in self.adj(v):
                if e.src == v:
                    cost += e.flow * e.cost
        return cost

    def __str__(self):
        s = ''
        for v in range(self.v):
            for e in self.adj(v):
                s += "{} {}\n".format(v, e)

        return s


def min_cost(network, s, t, f):
    def augment_path():
        def relax(edge, v):
            w = edge.other(v)
            c = edge.cost_from(v)
            if e.residual_capacity(v) > 0 and dists[w] > dists[v] + c:
                dists[w] = dists[v] + c
                edge_to[w] = e
                _nodes.append(w)

        dists = [WEIGHT_MAX] * network.v
        dists[s] = 0
        edge_to = [None] * network.v
        nodes = []

        nodes.append(s)
        for _ in range(network.v):
            _nodes = []
            for v in nodes:
                for e in network.adj(v):
                    relax(e, v)
            nodes = _nodes

        if edge_to[t] is None:
            return (0, [])
        else:
            v = t
            e = edge_to[v]
            cap = f
            while e is not None:
                v = e.other(v)
                _cap = e.residual_capacity(v)
                if cap > _cap:
                    cap = _cap
                e = edge_to[v]
            return (cap, edge_to)

    while f > 0:
        cap, path = augment_path()
        if cap == 0:
            break
        f -= cap
        v = t
        e = path[t]
        while e is not None:
            v = e.other(v)
            e.add_flow(v, cap)
            e = path[v]

    if f > 0:
        return -1
    else:
        return network.cost()


def run():
    v, e, f = [int(i) for i in input().split()]
    net = Network(v)
    s, t = 0, v-1

    for _ in range(e):
        v, w, c, d = [int(i) for i in input().split()]
        net.add(Edge(v, w, c, d))

    print(min_cost(net, s, t, f))


if __name__ == '__main__':
    run()

Solution (Python):

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    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 = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, rev) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v
                        prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res


import sys
readline = sys.stdin.readline
write = sys.stdout.write
N, M, F = map(int, readline().split())

mcf = MinCostFlow(N)
for i in range(M):
    u, v, c, d = map(int, readline().split())
    mcf.add_edge(u, v, c, d)
write("%d\n" % mcf.flow(0, N-1, F))