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:
#!usr/bin/env python3
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

# 1:shortest path
# 1_A
"""
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())
"""

# 1_B
"""
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())
"""
# 1_C
"""
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())
"""

# 2:spanning tree
# 2_A
"""
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)
"""

#2_B
"""
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
"""

#3:connected components
#3_A

#3_B

#3_C


#4:path/cycle
#4_A
"""
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)
"""

#4_B
"""
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)
"""

#5:tree
#5_A
"""
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))
"""

#5_B
"""
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))
"""
#5_C

#5_D

#5_E


#6
#6_A_maximum_flow
"""
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))
"""
#6_B
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))
#7
#7_A
"""
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))
"""

Submission status: Accepted

Solution code:
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):
        # edge[fro]: to, cap, cost, rev(逆辺)
        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:  # TODO: must be Verified
            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]
            #print(d, flow, prevVertex, prevEdge)
        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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_6_B: Minimum Cost Flow


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

Submission status: Accepted

Solution code:

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

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        visited = set()
        queue = [(0, source, tuple())]
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            if v in visited:
                continue
            elif v == sink:
                dist = total_cost
                edge_trace = edge_memo
                break
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and target not in visited:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))
        else:
            return -1

        aug = min(required_flow, min(e[0] for e in trace(source, edge_trace)))
        required_flow -= aug
        res += aug * dist
        for e in trace(source, edge_trace):
            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))

Submission status: Runtime Error

Solution code:
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, cap, cost, len(edges[s1])])
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
    answer += decreased * distance[sink]
    trace_i = sink
    while trace_i != 0:
        this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
        this_edge[1] -= decreased
        trace_i = before_vertice[trace_i]
        edges[trace_i][this_edge[3]][1] += decreased
    if flow <= 0:
        print(answer)
        break

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, used, all_weight, connect):
    max_weight = all_weight
    max_source = source
    used[source] = 1
    for target, weight in connect[source]:
        if not used[target]:
            now_weight = all_weight + weight
            this_source, this_weight = dfs(target, used, now_weight, connect)
            if max_weight < this_weight:
                max_weight = this_weight
                max_source = this_source
    return [max_source, max_weight]

vertice = int(input())
connect = defaultdict(list)
for _ in range(vertice - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight])
    connect[v2].append([v1, weight])
answer = 0
start_v = 0
for i in range(2):
    used = [0 for n in range(vertice)]
    start_v, answer = dfs(start_v, used, 0, connect)
print(answer)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
import sys
import csv
import argparse
import time
import heapq

INF = sys.maxint/3

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

    def print_attributes(self):
        print "to: {0}, cap: {1}, cost: {2}, rev: {3}".format(self.to, self.cap, self.cost, self.rev)

class MinimumCostFlow:

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

    def add_edge(self, s, t, cap, cost):
        forward_edge = Edge(t, cap, cost, len(self.G[t]))
        self.G[s].append(forward_edge)
        backward_edge = Edge(s, 0, -cost, len(self.G[s])-1)
        self.G[t].append(backward_edge)

    def print_edges(self):
        print "==== print edges ===="
        for i in range(self.V):
            print "\nedges from {}".format(i)
            for e in self.G[i]:
                e.print_attributes()

    def minimum_cost_flow(self, s, t, f):
        res = 0
        h = [0] * self.V

        while f>0:
            pque = []
            dist = [INF for i in range(self.V)]
            prev_v = [0 for i in range(self.V)]
            prev_e = [0 for i in range(self.V)]

            dist[s] = 0
            heapq.heappush(pque, (0, s))
            while(len(pque)!=0):
                p = heapq.heappop(pque)
                v = p[1]
                if (dist[v] < p[0]):
                    continue
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if (e.cap>0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]):
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prev_v[e.to] = v
                        prev_e[e.to] = i
                        heapq.heappush(pque, (dist[e.to], e.to))

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

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

            d = f

            v = t
            while v!=s:
                d = min(d, self.G[prev_v[v]][prev_e[v]].cap)
                v = prev_v[v]

            f -= d
            res += d * h[t]

            v = t
            while v!=s:
                e = self.G[prev_v[v]][prev_e[v]]
                e.cap -= d
                self.G[v][e.rev].cap += d
                v = prev_v[v]

        return res

def main():
    V, E, F = map(int, raw_input().split())
    mcf = MinimumCostFlow(V, E)
    for i in range(E):
        u, v, c, d = map(int, raw_input().split())
        mcf.add_edge(u, v, c, d)

    #print "minimum cost flow: {}".format(mcf.minimum_cost_flow(0, V-1, F))
    print mcf.minimum_cost_flow(0, V-1, F)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
import sys
import csv
import argparse
import time
import heapq

INF = sys.maxint/3

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

    def print_attributes(self):
        print "to: {0}, cap: {1}, cost: {2}, rev: {3}".format(self.to, self.cap, self.cost, self.rev)

class MinimumCostFlow:

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

    def add_edge(self, s, t, cap, cost):
        forward_edge = Edge(t, cap, cost, len(self.G[t]))
        self.G[s].append(forward_edge)
        backward_edge = Edge(s, 0, -cost, len(self.G[s])-1)
        self.G[t].append(backward_edge)

    def print_edges(self):
        print "==== print edges ===="
        for i in range(self.V):
            print "\nedges from {}".format(i)
            for e in self.G[i]:
                e.print_attributes()

    def minimum_cost_flow(self, s, t, f):
        res = 0
        h = [0] * self.V

        while f>0:
            pque = []
            dist = [INF for i in range(self.V)]
            prev_v = [0 for i in range(self.V)]
            prev_e = [0 for i in range(self.V)]

            dist[s] = 0
            heapq.heappush(pque, (0, s))
            while(len(pque)!=0):
                p = heapq.heappop(pque)
                v = p[1]
                if (dist[v] < p[0]):
                    continue
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if (e.cap>0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]):
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prev_v[e.to] = v
                        prev_e[e.to] = i
                        heapq.heappush(pque, (dist[e.to], e.to))

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

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

            d = f

            v = t
            while v!=s:
                d = min(d, self.G[prev_v[v]][prev_e[v]].cap)
                v = prev_v[v]

            f -= d
            res += d * h[t]

            v = t
            while v!=s:
                e = self.G[prev_v[v]][prev_e[v]]
                e.cap -= d
                self.G[v][e.rev].cap += d
                v = prev_v[v]

        return res

def main():
    V, E, F = map(int, raw_input().split())
    mcf = MinimumCostFlow(V, E)
    for i in range(E):
        u, v, c, d = map(int, raw_input().split())
        mcf.add_edge(u, v, c, d)

    #print "minimum cost flow: {}".format(mcf.minimum_cost_flow(0, V-1, F))
    print mcf.minimum_cost_flow(0, V-1, F)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
'''
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
import sys
import csv
import argparse
import time
'''
import heapq

INF = sys.maxint/3

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

    def print_attributes(self):
        print "to: {0}, cap: {1}, cost: {2}, rev: {3}".format(self.to, self.cap, self.cost, self.rev)

class MinimumCostFlow:

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

    def add_edge(self, s, t, cap, cost):
        forward_edge = Edge(t, cap, cost, len(self.G[t]))
        self.G[s].append(forward_edge)
        backward_edge = Edge(s, 0, -cost, len(self.G[s])-1)
        self.G[t].append(backward_edge)

    def print_edges(self):
        print "==== print edges ===="
        for i in range(self.V):
            print "\nedges from {}".format(i)
            for e in self.G[i]:
                e.print_attributes()

    def minimum_cost_flow(self, s, t, f):
        res = 0
        h = [0] * self.V

        while f>0:
            pque = []
            dist = [INF for i in range(self.V)]
            prev_v = [0 for i in range(self.V)]
            prev_e = [0 for i in range(self.V)]

            dist[s] = 0
            heapq.heappush(pque, (0, s))
            while(len(pque)!=0):
                p = heapq.heappop(pque)
                v = p[1]
                if (dist[v] < p[0]):
                    continue
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if (e.cap>0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]):
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prev_v[e.to] = v
                        prev_e[e.to] = i
                        heapq.heappush(pque, (dist[e.to], e.to))

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

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

            d = f

            v = t
            while v!=s:
                d = min(d, self.G[prev_v[v]][prev_e[v]].cap)
                v = prev_v[v]

            f -= d
            res += d * h[t]

            v = t
            while v!=s:
                e = self.G[prev_v[v]][prev_e[v]]
                e.cap -= d
                self.G[v][e.rev].cap += d
                v = prev_v[v]

        return res

def main():
    V, E, F = map(int, raw_input().split())
    mcf = MinimumCostFlow(V, E)
    for i in range(E):
        u, v, c, d = map(int, raw_input().split())
        mcf.add_edge(u, v, c, d)

    #print "minimum cost flow: {}".format(mcf.minimum_cost_flow(0, V-1, F))
    print mcf.minimum_cost_flow(0, V-1, F)

if __name__ == '__main__':
    main()