Problem p02949 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 5 + 5)


def omit(n, links, parents):
    q = [0]
    visited_f = [False] * n
    while q:
        v = q.pop()
        if visited_f[v]:
            continue
        visited_f[v] = True
        q.extend(u for u in links[v] if not visited_f[u])

    q = [n - 1]
    visited_b = [False] * n
    while q:
        v = q.pop()
        if visited_b[v]:
            continue
        visited_b[v] = True
        q.extend(u for u in parents[v] if not visited_b[u])

    remains = [i for i, (f, b) in enumerate(zip(visited_f, visited_b)) if f and b]
    sr = set(remains)
    for v in remains:
        links[v] &= sr

    return remains


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
costs = [[INF] * n for _ in range(n)]
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
remains = omit(n, links, parents)

dist = [INF] * n
dist[0] = 0
for _ in range(n + 1):
    updated = False
    for v in remains:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    # print(dist, updated)
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 5 + 5)


def omit(n, links, parents):
    def remove_child(v):
        for u in parents[v]:
            if u == v:
                continue
            links[u].remove(v)
            ps = links[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_child(u)

    def remove_parent(v):
        for u in links[v]:
            if u == v:
                continue
            parents[u].remove(v)
            ps = parents[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_parent(u)

    drop = [False] * n
    for v, s in enumerate(links):
        if v == n - 1:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_child(v)

    for v, s in enumerate(parents):
        if v == 0:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_parent(v)

    # print(drop)
    # print(links)
    # print(parents)

    return drop


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
costs = [[INF] * n for _ in range(n)]
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
drop = omit(n, links, parents)

remains = [v for v, f in enumerate(drop) if f == False]

dist = [INF] * n
dist[0] = 0
for _ in range(n + 1):
    updated = False
    for v in remains:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    # print(dist, updated)
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))

Buggy submission (verdict: Runtime Error):
import sys


def omit(n, links, parents):
    def remove_child(v):
        for u in parents[v]:
            if u == v:
                continue
            links[u].remove(v)
            ps = links[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_child(u)

    def remove_parent(v):
        for u in links[v]:
            if u == v:
                continue
            parents[u].remove(v)
            ps = parents[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_parent(u)

    drop = [False] * n
    for v, s in enumerate(links):
        if v == n - 1:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_child(v)

    for v, s in enumerate(parents):
        if v == 0:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_parent(v)

    # print(drop)
    # print(links)
    # print(parents)

    return drop


n, m, p = list(map(int, input().split()))
INF = 10 ** 12
costs = [[INF] * n for _ in range(n)]
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
drop = omit(n, links, parents)

remains = [v for v, f in enumerate(drop) if f == False]

dist = [INF] * n
dist[0] = 0
for _ in range(n):
    updated = False
    for v in remains:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    # print(dist, updated)
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))

Buggy submission (verdict: Runtime Error):
import sys


def omit(n, links, parents):
    def remove_child(v):
        for u in parents[v]:
            if u == v:
                continue
            links[u].remove(v)
            ps = links[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_child(u)

    def remove_parent(v):
        for u in links[v]:
            if u == v:
                continue
            parents[u].remove(v)
            ps = parents[u]
            if not ps or (len(ps) == 1 and list(ps)[0] == u):
                drop[u] = True
                remove_parent(u)

    drop = [False] * n
    for v, s in enumerate(links):
        if v == n - 1:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_child(v)

    for v, s in enumerate(parents):
        if v == 0:
            continue
        if not s or (len(s) == 1 and list(s)[0] == v):
            drop[v] = True
            remove_parent(v)

    # print(drop)
    # print(links)
    # print(parents)

    return drop


n, m, p = list(map(int, input().split()))
INF = 10 ** 9
costs = [[INF] * n for _ in range(n)]
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
for line in sys.stdin:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    parents[b].add(a)
    costs[a][b] = min(costs[a][b], p - c)
drop = omit(n, links, parents)

remains = [v for v, f in zip(range(n), drop) if f == False]

dist = [INF] * n
dist[0] = 0
for _ in range(m):
    updated = False
    for v in remains:
        d = dist[v]
        if d == INF:
            continue
        cv = costs[v]
        for u in links[v]:
            if dist[u] > d + cv[u]:
                dist[u] = d + cv[u]
                updated = True
    if not updated:
        break
else:
    print(-1)
    exit()

print(max(0, -dist[n - 1]))