Problem p03020 (python)

Fixed submission:
from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))

Buggy submission (verdict: Runtime Error):
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

E = []
N = int(input())
su = 0
inf = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + inf))
    E.append((i, 2*N+1, cnt, x - y + inf))
    E.append((i, 2*N+2, cnt, - x + y + inf))
    E.append((i, 2*N+3, cnt, - x - y + inf))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + inf))
    E.append((2*N+1, i+N, cnt, - x + y + inf))
    E.append((2*N+2, i+N, cnt, x - y + inf))
    E.append((2*N+3, i+N, cnt, x + y + inf))

print(su * inf * 2 - min_cost_flow_dijkstra(E, 2*N+4, 2*N+5, su))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    NN = 2 * N + 6
    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
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        q = []
        heappush(q, s)
        while h:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == 1<<100:
            return -1
        for v in range(NN):
            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 * h[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

E = []
N = int(input())
su = 0
INF = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow(E, 2*N+4, 2*N+5, su))

Buggy submission (verdict: Runtime Error):
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    NN = 2 * N + 6
    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
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        q = []
        heappush(q, s)
        while h:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == 1<<100:
            return -1
        for v in range(NN):
            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 * h[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

E = []
N = int(input())
su = 0
INF = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow(E, 2*N+4, 2*N+5, su))