Problem p02949 (python)

Fixed submission:
from collections import deque
NegInf = -float('inf')


n, m, p = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1].append((b-1, c-p))


def bellman_ford(vst, graph, node_num, NegInf):
    costs = [NegInf] * node_num
    costs[0] = 0
    v_nows = set([vst])
    for _ in range(n):
        v_changeds = set()
        for v_from in v_nows:
            for v_to, cost in graph[v_from]:
                c2 = costs[v_from] + cost
                if c2 > costs[v_to]:
                    costs[v_to] = c2
                    v_changeds.add(v_to)
        v_nows = v_changeds



    if not v_changeds:
        return costs

    for i in v_nows:
        costs[i] = NegInf

    que = deque(v_nows)
    while que:
        v_from = que.popleft()
        for v_to, cost in graph[v_from]:
            if costs[v_to] != NegInf:
                costs[v_to] = NegInf
                que.append(v_to)
    return costs


costs = bellman_ford(0, graph, n, -float('inf'))
if costs[n-1] == NegInf:
    print(-1)
else:
    print(max(0, costs[n-1]))

Buggy submission (verdict: Runtime Error):
from collections import deque


n, m, p = map(int, input().split())
graph = [[-float('inf')] * n for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c - p


def bellman_ford(vst, graph, node_num):
    costs = [-float('inf')] * n
    costs[0] = 0
    update_points = []
    ans = 0
    v_nows = set([vst])
    for _ in range(n):
        v_changeds = set()
        for v_from in v_nows:
            for v_to, cost in enumerate(graph[v_from]):
                if cost == -float('inf'):
                    continue
                if costs[v_from] + cost > costs[v_to]:
                    costs[v_to] = costs[v_from] + cost
                    v_changeds.add(v_to)



    if not v_changeds:
        return costs


    que = deque()
    que.append(start)
    while que:
        edges = que.popleft()
        for to, costs in enumerate(graph[edges]):
            if costs != -float('inf'):
                graph[edges] = -float('inf')
                que.append(to)
    return costs



costs = bellman_ford(0, graph, n)
if costs[n-1] == -float('inf'):
    print(-1)
else:
    print(max(0, costs[n-1]))

Buggy submission (verdict: Runtime Error):
from collections import deque


n, m, p = map(int, input().split())
graph = [[-float('inf')] * n for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c



def dfs(graph, start, goal):
    que = deque()
    que.append(start)
    reached = set()
    while que:
        edges = que.popleft()
        for to, cost in enumerate(graph[edges]):
            if cost != -float('inf') and to not in reached:
                que.append(to)
                reached.add(to)
    if goal in reached:
        return True
    else:
        return False


dist = [-float('inf')] * n
dist[0] = 0
ans = -float('inf')
flag = True
for time in range(1, n+1):
    if not flag:
        break
    new_dist = [-float('inf')] * n
    flag = False
    for before, edges in enumerate(graph):
        for to, cost in enumerate(edges):
            if dist[before] + cost > new_dist[to]:
                new_dist[to] = dist[before] + cost
                flag = True
                if time == n:
                    update_points = []
                    update_points.append(to)
    dist = new_dist
    ans = max(0, new_dist[n-1] - time * p, ans)



flag = False
for i in update_points:
    if dfs(graph, i, n-1):
        print(-1)
        break
else:
    print(ans)