Problem p02949 (python)

Fixed submission:
def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra, bellman_ford, csgraph_from_dense, NegativeCycleError

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

ABC = [(a - 1, b - 1, c)for a, b, c in zip(*[iter(ABC)] * 3)]

D = [[0] * N for _ in range(N)]
for a, b, c in ABC:
    D[a][b] = c

T = dijkstra(D)

E = [[0] * N for _ in range(N)]
for a, b, c in ABC:
    if T[0][a] < INF and T[b][N - 1] < INF:
        E[a][b] = P - c

try:
    G = bellman_ford(csgraph_from_dense(E))
    ans = max(0, -int(G[0][N - 1]))
except NegativeCycleError:
    ans = -1

print(ans)

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra, bellman_ford, csgraph_from_dense, NegativeCycleError
from itertools import permutations

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

D = [INF] * (N + 1)
D[1] = 0

loop = False
for i in range(2 * N + 100):
    for a, b, c in zip(*[iter(ABC)] * 3):
        d = D[a] + P - c
        if D[b] > d:
            D[b] = d
            if b == N and i > N:
                loop = True

print(-1 if loop else max(0, -D[N]))

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra, bellman_ford, csgraph_from_dense, NegativeCycleError
from itertools import permutations

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

D = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    D[a - 1][b - 1] = c

T = dijkstra(D)

E = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    if T[b - 1][N - 1] < INF:
        E[a - 1][b - 1] = P - c

try:
    G = bellman_ford(csgraph_from_dense(E), indices=0)
    ans = max(0, -int(G[N - 1]))
except NegativeCycleError:
    ans = -1

print(ans)

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra, bellman_ford, csgraph_from_dense, NegativeCycleError
from itertools import permutations

INF = float("inf")

N, M, P, *ABC = map(int, open(0).read().split())

D = [[0] * N for _ in range(N)]
E = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    D[a - 1][b - 1] = c
    E[a - 1][b - 1] = P - c

T = dijkstra(D)
for a, b in permutations(range(N), 2):
    if T[b][N - 1] == INF:
        E[a][b] = 0

try:
    G = bellman_ford(csgraph_from_dense(E), indices=0)
    ans = max(0, -int(G[N - 1]))
except NegativeCycleError:
    ans = -1

print(ans)