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):
INF = float('inf')


def trace_back(sink, predecessors):
    p = predecessors[sink]
    while p is not None:
        v, i = p
        yield edges[v][i]
        p = predecessors[v]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        dist = [INF] * n
        dist[source] = 0
        predecessors = [None] * n

        while True:
            updated = False
            for v in range(n):
                if dist[v] == 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] == INF:
            return -1

        aug = min(required_flow, min(e[0] for e in trace_back(sink, predecessors)))
        required_flow -= aug
        res += 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


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 heapq


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

    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    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 run(self, source, sink, f, INF=10**5):
        res = 0
        h, prevv, preve = [0] * self.V, [0] * self.V, [0] * self.V
        while (f > 0):
            pque = []
            dist = [INF] * self.V
            dist[source] = 0
            heapq.heappush(pque, (0, source))
            while pque:
                cost, v = heapq.heappop(pque)
                cost = -cost
                if dist[v] < cost:
                    continue
                for i, e in enumerate(self.E[v]):
                    if e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]:
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prevv[e.to], preve[e.to] = v, i
                        heapq.heappush(pque, (-dist[e.to], e.to))
            if dist[sink] == INF:
                return -1
            for v in range(self.V):
                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

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

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

    def addEdge(self, f, t, cap, cost):
        
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**9+7

        res = 0
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            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

n, m, f = map(int, input().split())
graph = MinCostFlow(n)
for i in range(m):
    u, v, c, d = map(int, input().split())
    graph.addEdge(u, v, c, d)
print(graph.minCostFlow(0, n-1, f))

Solution (Python):
from collections import defaultdict

v_num, e_num, flow = (int(n) for n in input().split(" "))
edges = defaultdict(list)
for _ in range(e_num):
    s1, t1, cap, cost = (int(n) for n in input().split(" "))
    edges[s1].append([t1, cap, cost, len(edges[t1])])
    edges[t1].append([s1, 0, -cost, len(edges[s1]) - 1])
answer = 0
before_vertice = [float("inf") for n in range(v_num)]
before_edge = [float("inf") for n in range(v_num)]
sink = v_num - 1
while True:
    distance = [float("inf") for n in range(v_num)]
    distance[0] = 0
    updated = 1
    while updated:
        updated = 0
        for v in range(v_num):
            if distance[v] == float("inf"):
                continue
            for i, (target, cap, cost, trace_i) in enumerate(edges[v]):
                if cap > 0 and distance[target] > distance[v] + cost:
                    distance[target] = distance[v] + cost
                    before_vertice[target] = v
                    before_edge[target] = i
                    updated = 1
    if distance[sink] == float("inf"):
        print(-1)
        break
    decreased = flow
    trace_i = sink
    while trace_i != 0:
        decreased = min(decreased, edges[before_vertice[trace_i]][before_edge[trace_i]][1])
        trace_i = before_vertice[trace_i]
    flow -= decreased
    trace_i = sink
    while trace_i != 0:
        this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
        this_edge[1] -= decreased
        answer += this_edge[2] * decreased
        edges[trace_i][this_edge[3]][1] += decreased
        trace_i = before_vertice[trace_i]
    if flow <= 0:
        print(answer)
        break

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class Edge():
    def __init__(self,t,f,r,ca,co):
        self.to = t
        self.fron = f
        self.rev = r
        self.cap = ca
        self.cost = co

class MinCostFlow():
    size = 0
    graph = []

    def __init__(self, s):
        self.size = s
        self.graph = [[] for _ in range(s)]

    def add_edge(self, f, t, ca, co):
        self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
        self.graph[t].append(Edge(f, t, len(self.graph[f])-1, 0, -co))

    def min_path(self, s, t):
        dist = [inf] * self.size
        route = [None] * self.size
        que = collections.deque()
        inq = [False] * self.size
        dist[s] = 0
        que.append(s)
        inq[s] = True
        while que:
            u = que.popleft()
            inq[u] = False
            for e in self.graph[u]:
                if e.cap == 0:
                    continue
                v = e.to
                if dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    route[v] = e
                    if not inq[v]:
                        que.append(v)
                        inq[v] = True

        if dist[t] == inf:
            return inf, 0

        flow = inf
        v = t
        while v != s:
            e = route[v]
            if flow > e.cap:
                flow = e.cap
            v = e.fron

        c = 0
        v = t
        while v != s:
            e = route[v]
            e.cap -= flow
            self.graph[e.to][e.rev].cap += flow
            c += e.cost * flow
            v = e.fron

        return dist[t], flow

    def calc_min_cost_flow(self, s, t, flow):
        total_cost = 0
        while flow > 0:
            c,f = self.min_path(s, t)
            if f == 0:
                return inf
            f = min(flow, f)
            total_cost += c * f
            flow -= f

        return total_cost


def main():
    n,m,f = LI()
    uvcd = [LI() for _ in range(m)]

    mf = MinCostFlow(n)
    for u,v,c,d in uvcd:
        mf.add_edge(u,v,c,d)

    r = mf.calc_min_cost_flow(0, n-1, f)
    if r == inf:
        return -1

    return r


print(main())

Solution (Python):
import heapq

class edge:
    def __init__(self, to, cap, cost, rev):
        self.to: int = to
        self.cap: int = cap
        self.cost: int = cost
        self.rev: int = rev


class min_cost_flow:
    def __init__(self, N):
        self.N: int = N
        self.INF: int = 1000000000000000000
        self.G = [[] for i in range(N)]
        
    def add_edge(self, fro, to, cap, cost):
        self.G[fro].append(edge(to, cap, int(cost), int(len(self.G[to]))))
        self.G[to].append(edge(fro, 0, -int(cost), int(len(self.G[fro]) - 1)))
        
    def solve(self, s, t, f):
        N = self.N
        prevv = [0 for i in range(N)]
        preve = [0 for i in range(N)]
        
        ret = 0
        while 0 < f:
            dist = [self.INF for i in range(N)]
            dist[s] = 0
            hq = [(0, s)]
            heapq.heapify(hq)
            while hq:
                d, v = heapq.heappop(hq)
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if 0 < e.cap and dist[v] + e.cost < dist[e.to]:
                        dist[e.to] = dist[v] + e.cost
                        prevv[e.to] = v
                        preve[e.to] = i
                        heapq.heappush(hq, (dist[e.to], e.to))

            
            if dist[t] == self.INF:
                return self.INF

            d = f
            v = t
            while v != s:
                d = min(d, self.G[prevv[v]][preve[v]].cap)
                v = prevv[v]

            f -= d
            ret += d * dist[t]
            v = t
            while v != s:
                e = self.G[prevv[v]][preve[v]]
                e.cap -= d
                self.G[v][e.rev].cap += d
                v = prevv[v]
    
        return ret


v, e, f = map(int, input().split())
mcf = min_cost_flow(v)
for i in range(e):
    ui, vi, ci, di = map(int, input().split())
    mcf.add_edge(ui, vi, ci, di)
    
ans = mcf.solve(0, v-1, f)
if ans == mcf.INF:
    print(-1)
else:
    print(ans)

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

Solution (Python):
from heapq import heappush, heappop

class MinimumCostFlow:
    inf = 1000000000
    def __init__(self, n):
        self.n = n
        self.edges = [[] for i in range(n)]
    def add_edge(self, f, t, cap, cost):
        self.edges[f].append([t, cap, cost, len(self.edges[t]), False])
        self.edges[t].append([f, 0, -cost, len(self.edges[f]) - 1, True]) 
    def flow(self, s, t, flow):
        n = self.n
        g = self.edges
        inf = MinimumCostFlow.inf

        prevv = [0 for i in range(n)]
        preve = [0 for i in range(n)]
        h = [0 for i in range(n)]
        dist = [inf for i in range(n)]

        res = 0

        while flow != 0:
            dist = [inf for i in range(n)]
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                r0 = dist[v] + h[v]
                for i, e in enumerate(g[v]):
                    w, cap, cost, _, _ = e
                    if cap > 0 and r0 + cost - h[w] < dist[w]:
                        r = r0 + cost - h[w]
                        dist[w] = r
                        prevv[w] = v
                        preve[w] = i
                        heappush(que, (r, w))

            if dist[t] == inf:
                return -1
            
            for i in range(n):
                h[i] += dist[i]

            d = flow
            v = t
            while v != s:
                d = min(d, g[prevv[v]][preve[v]][1])
                v = prevv[v]
            flow -= d
            res += d * h[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

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

mcf = MinimumCostFlow(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))

Solution (Python):

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,f = map(int,readline().split())
"""
n頂点m辺の重み付き有向グラフに流量fを流したい。
コストの最小値を出力せよ。
但しsourse = 0,sink = n-1とし、
そもそも流量f流せるだけcapacityがない場合は-1を出力せよ。
"""

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

    def addEdge(self, f, t, cap, cost): 
        
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f): 
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**18

        res = 0 
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            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

MCF = MinCostFlow(n)
for i in range(m):
    u,v,cap,cost = map(int,readline().split())
    MCF.addEdge(u,v,cap,cost)

print(MCF.minCostFlow(0,n-1,f))

Solution (Python):
from heapq import *


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

Solution (Python):
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):
        
        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 
        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 
        while flow > 0:
            self.dijkstra(start)
            if self.dist[finish] == self.INF: return -1 
            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))

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

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

Solution (Python):









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


capacityG = {i:{} for i in range(V)} 
costG = {i:{} for i in range(V)} 

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 
        cur = p[cur]
print(total_cost)

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