Problem p02949 (python)

Fixed submission:
def main():
    from itertools import product
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    adj_list = [[] for _ in range(N)]
    radj_list = [[] for _ in range(N)]
    ok = [False]*N
    edge = []
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        adj_list[a-1].append(b-1)
        radj_list[b-1].append(a-1)
        edge.append((a-1, b-1, -c))

    def dfs(G, v):
        seen = [False]*N
        todo = [v]
        seen[v] = True
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return seen

    i = 0
    for s, rs in zip(dfs(adj_list, 0), dfs(radj_list, N-1)):
        ok[i] = s and rs
        i += 1

    # Bellman_ford
    d = [10**12]*N
    d[0] = 0
    update = True
    step = 0
    while update:
        update = False
        for a, b, c in edge:
            if not(ok[a]) or not(ok[b]):
                continue
            newD = d[a] + c
            if newD < d[b]:
                update = True
                d[b] = newD
        step += 1
        if step > N:
            return print(-1)
    print(max(0, d[N-1]*-1))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred)


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


def main():
    from scipy.sparse.csgraph import bellman_ford
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import NegativeCycleError
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    g = [[10**6]*N for _ in range(N)]
    ban_v = set()
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        if a == b:
            ban_v.add(a-1)
        else:
            g[a-1][b-1] = -c

    csr = csr_matrix(g)
    ans = -1
    try:
        dist, p = bellman_ford(csr, indices=0, return_predecessors=True)
        path = get_path(0, N-1, p)
        if any(v in ban_v for v in path):
            ans = -1
        else:
            ans = max(0, int(dist[N-1]*-1))
    except NegativeCycleError:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred)


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


def main():
    from scipy.sparse.csgraph import bellman_ford
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import NegativeCycleError
    from itertools import product
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    g = [[10**6]*N for _ in range(N)]
    adj_list = [[] for _ in range(N)]
    radj_list = [[] for _ in range(N)]
    ok = [False]*N
    ban_v = set()
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        if a == b:
            ban_v.add(a-1)
        else:
            g[a-1][b-1] = -c
            adj_list[a-1].append(b-1)
            radj_list[b-1].append(a-1)

    def dfs(G, v):
        seen = [False]*N
        todo = [v]
        seen[v] = True
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return seen

    for i, s, rs in product(range(N), dfs(adj_list, 0), dfs(radj_list, N-1)):
        if s and rs:
            ok[i] = True

    for i in range(N):
        if ok[i]:
            continue
        for j in range(N):
            g[i][j] = 10**6

    csr = csr_matrix(g)
    ans = -1
    try:
        dist, p = bellman_ford(csr, indices=0, return_predecessors=True)
        path = get_path(0, N-1, p)
        if any(v in ban_v for v in path):
            ans = -1
        else:
            ans = max(0, int(dist[N-1]*-1))
    except NegativeCycleError:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred)


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


def main():
    from scipy.sparse.csgraph import bellman_ford
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import NegativeCycleError
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    g = [[10**6]*N for _ in range(N)]
    ban_v = set()
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        if a == b:
            ban_v.add(a-1)
        else:
            g[a-1][b-1] = -c

    csr = csr_matrix(g)
    ans = -1
    try:
        dist, p = bellman_ford(csr, indices=0, return_predecessors=True)
        path = get_path(0, N-1, p)
        if any(v in ban_v for v in path):
            ans = -1
        else:
            ans = max(0, int(dist[N-1]*-1))
    except NegativeCycleError:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


def main():
    from scipy.sparse.csgraph import bellman_ford
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph._shortest_path import NegativeCycleError
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    g = [[10**6]*N for _ in range(N)]
    ban_v = set()
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        if a == b:
            ban_v.add(a-1)
        else:
            g[a-1][b-1] = -c

    csr = csr_matrix(g)
    ans = -1
    try:
        dist, p = bellman_ford(csr, return_predecessors=True)
        path = get_path(0, N-1, p)
        if any(v in ban_v for v in path):
            ans = -1
        else:
            ans = max(0, int(dist[0][N-1]*-1))
    except NegativeCycleError:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()