Problem p02949 (python)

Fixed submission:
from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M, P = [int(a) for a in input().split()]
    ABC = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    FORWARD = defaultdict(lambda: [])
    BACK = defaultdict(lambda: [])
    for a, b, c in ABC:
        t = FORWARD[a]
        t.append((b, c))
        FORWARD[a] = t

        t = BACK[b]
        t.append((a, c))
        BACK[b] = t

    mem = {N}
    q = [N]
    while len(q) != 0:
        t = q.pop()
        for t2, _ in BACK[t]:
            if t2 in mem:
                continue
            q.append(t2)
            mem.add(t2)

    ABC = [(a, b, P - c) for a, b, c in ABC if a in mem and b in mem]

    table = [MAX] * (N + 1)
    history_table = [set() for _ in range(N + 1)]
    table[1] = 0
    # history_table[1] = {1}
    # table2 = [-1] * N
    for _ in range(len(mem)):
        for a, b, c in ABC:
            if table[a] == MAX:
                continue
            if table[a] + c < table[b]:
                # if b in history_table[a]:
                #     print(-1)
                #     return
                table[b] = table[a] + c
                # h2 = set(history_table[a])
                # h2.add(b)
                # history_table[b] = h2
    for a, b, c in ABC:
        if table[a] == MAX:
            continue
        if table[a] + c < table[b]:
            print(-1)
            return
    print(max(0, -table[N]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M, P = [int(a) for a in input().split()]
    ABC = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    ABC = [(a, b, P - c) for a, b, c in ABC]

    table = [MAX] * (N + 1)
    table[1] = 0
    for _ in range(N):
        for a, b, c in ABC:
            if table[a] == MAX:
                continue
            if table[a] + c < table[b]:
                table[b] = table[a] + c
    if -table[N] < 0:
        print(0)
        return
    score = -table[N]
    for a, b, c in ABC:
        if table[a] == MAX:
            continue
        if table[a] + c < table[b]:
            table[b] = table[a] + c
    if -table[N] != score:
        raise ValueError()
        print(-1)
        return
    print(-table[N])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M, P = [int(a) for a in input().split()]
    ABC = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    FORWARD = defaultdict(lambda: [])
    BACK = defaultdict(lambda: [])
    for a, b, c in ABC:
        t = FORWARD[a]
        t.append((b, c))
        FORWARD[a] = t

        t = BACK[b]
        t.append((a, c))
        BACK[b] = t

    mem = {N}
    q = [N]
    while len(q) != 0:
        t = q.pop()
        for t2, _ in BACK[t]:
            if t2 in mem:
                continue
            q.append(t2)
            mem.add(t2)

    # print(mem)
    poss = [(1, 0, {1})]

    table = [MIN] * N
    # table2 = [-1] * N
    for _ in range(5001):
        local_table = [(MIN, None)] * N
        for pos, score, history in poss:
            for nxt, s2 in FORWARD[pos]:
                if nxt not in mem:
                    continue
                if nxt in history and score + s2 - P > table[nxt - 1]:
                    print(-1)
                    return
                if score + s2 - P > local_table[nxt - 1][0]:
                    h2 = {*history}
                    h2.add(nxt)
                    local_table[nxt - 1] = score + s2 - P, h2
                # table2[nxt - 1] = history
                table[nxt - 1] = max(score + s2 - P, table[nxt - 1])
        newposs = []
        for i, (s, his) in enumerate(local_table):
            if s == MIN:
                continue
            newposs.append((i + 1, s, his))
        poss = newposs
    print(max(0, table[N - 1]))


if __name__ == '__main__':
    main()