Problem p02949 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

n, m, p = map(int, input().split())

edges = []
routes  = [[] for i in range(n)]
rev_routes = [[] for i in range(n)]
from_start = set()
to_goal = set()

def dfs(node, routes, seen):
    if node in seen:
        return
    seen.add(node)
    candidates = routes[node]
    for to in candidates:
        dfs(to, routes, seen)


for _ in range(m):
    node1, node2, value = map(int, input().split())
    node1, node2, value = node1-1, node2-1, value - p
    edges.append([node1, node2, value])
    routes[node1].append(node2)
    rev_routes[node2].append(node1)

dfs(0, routes, from_start)
dfs(n-1, rev_routes, to_goal)

from_start_to_goal = from_start & to_goal

graph = [-float('INF')] * n
graph[0] = 0

for i in range(n):
    is_updated = False
    for node, to, value in edges:
        if node not in from_start_to_goal or to not in from_start_to_goal:
            continue
        current_point = graph[node]
        next_point = graph[node] + value
        if graph[to] < next_point:
            graph[to] = next_point
            is_updated = True
        else:
            continue
    if not is_updated:
        score = max(0, graph[n-1])
        break
else:
    score = -1
      
print(score)

Buggy submission (verdict: Runtime Error):
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]


    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen


    for _ in range(m):
        node1, node2, value = map(int, input().split())
        node1, node2, value = node1 - 1, node2 - 1, value - p
        edges.append([node1, node2, value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    if n-1 not in from_start:
        print(-1)
        return

    to_goal = get_reachable_nodes(n-1, rev_routes)

    from_start_to_goal = from_start & to_goal

    matrix = [[10**6] * n for _ in range(n)]

    for row, col, value in edges:
        if {row, col} <= from_start_to_goal:
            if -value < matrix[row][col]:
                matrix[row][col] = -value

    graph = coo_matrix(matrix)
    try:
        bf = bellman_ford(graph, indices=[0])
        print(max(0, -int(bf[0][n - 1])))
    except NegativeCycleError:
        print(-1)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]


    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen


    for _ in range(m):
        node1, node2, value = map(int, input().split())
        node1, node2, value = node1 - 1, node2 - 1, value - p
        edges.append([node1, node2, value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    if n-1 not in from_start:
        print(-1)
        return

    to_goal = get_reachable_nodes(n-1, rev_routes)

    from_start_to_goal = from_start & to_goal

    values = []
    rows = []
    cols = []

    for row, col, value in edges:
        if {row, col} <= from_start_to_goal:
            rows.append(row)
            cols.append(col)
            values.append(-value)

    graph = coo_matrix((values, (rows, cols)))
    try:
        bf = bellman_ford(graph, indices=[0])
        print(max(0, -int(bf[0][n - 1])))
    except NegativeCycleError:
        print(-1)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
n, m, p = map(int, input().split())

edges = []
routes  = [[] for i in range(n)]
rev_routes = [[] for i in range(n)]
from_start = set()
to_goal = set()

def dfs(node, routes, seen):
    if node in seen:
        return
    seen.add(node)
    candidates = routes[node]
    for to in candidates:
        dfs(to, routes, seen)


for _ in range(m):
    node1, node2, value = map(int, input().split())
    node1, node2, value = node1-1, node2-1, value - p
    edges.append([node1, node2, value])
    routes[node1].append(node2)
    rev_routes[node2].append(node1)

dfs(0, routes, from_start)
dfs(n-1, rev_routes, to_goal)

from_start_to_goal = from_start & to_goal

graph = [-float('INF')] * n
graph[0] = 0

for i in range(n):
    is_updated = False
    for node, to, value in edges:
        if node not in from_start_to_goal or to not in from_start_to_goal:
            continue
        current_point = graph[node]
        next_point = graph[node] + value
        if graph[to] < next_point:
            graph[to] = next_point
            is_updated = True
        else:
            continue
    if not is_updated:
        score = max(0, graph[n-1])
        break
else:
    score = -1
      
print(score)