Problem p02949 (python)

Fixed submission:
import sys
N, M, P = [int(x) for x in input().split()]
forward = {}
backward = {}
for _ in range(M):
  A, B, C = [int(x) for x in input().split()]
  forward[A] = forward.get(A, {})
  if B in forward[A]:
    forward[A][B] = max(forward[A][B], C-P)
  else:
    forward[A][B] = C-P
  backward[B] = backward.get(B, {})
  if A in backward[B]:
    backward[B][A] = max(backward[B][A], C-P)
  else:
    backward[B][A] = C-P
#print(forward)
#print(backward)
reachable = set([N])
to_track = set([N])
while to_track:
  x = to_track.pop()
  if x not in backward:
    continue
  for y in backward[x]:
    if y not in reachable:
      to_track.add(y)
      reachable.add(y)
#print(reachable)
if 1 not in reachable:
  print(-1)
  sys.exit()

forward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
           for k, v in forward.items() if k in reachable}
#print(forward)
# backward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
#            for k, v in backward.items() if k in reachable}
#print(backward)

dist = {k: -float('inf') for k in reachable} 
dist[1] = 0
#print(reachable)
#print(dist)
#print(forward)
for _ in range(len(reachable)):
  renewed = False
  for x, y_dict in forward.items():
    for y in y_dict:
 #     print(x, y, forward[x][y], dist[x], dist[y])
      if dist[y] < dist[x] + forward[x][y]:
        renewed = True
        dist[y] = dist[x] + forward[x][y]
if renewed:
  # print('loop')
  print(-1)
else:
  print(max(0,dist[N]))

Buggy submission (verdict: Runtime Error):
import sys
N, M, P = [int(x) for x in input().split()]
forward = {}
backward = {}
for _ in range(M):
  A, B, C = [int(x) for x in input().split()]
  forward[A] = forward.get(A, {})
  if B in forward[A]:
    forward[A][B] = max(forward[A][B], C-P)
  else:
    forward[A][B] = C-P
  backward[B] = backward.get(B, {})
  if A in backward[B]:
    backward[B][A] = max(backward[B][A], C-P)
  else:
    backward[B][A] = C-P
#print(forward)
#print(backward)
reachable = set([N])
to_track = set([N])
while to_track:
  x = to_track.pop()
  if x not in backward:
    continue
  for y in backward[x]:
    if y not in reachable:
      to_track.add(y)
      reachable.add(y)
#print(reachable)
if 1 not in reachable:
  print(-1)
  sys.exit()

forward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
           for k, v in forward.items() if k in reachable}
#print(forward)
# backward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
#            for k, v in backward.items() if k in reachable}
#print(backward)


reached = [0]  # score is not negative
def dfs(x, point, visited):
  #print(x,point,visited)
  if x == N:
    reached.append(point)
  if x not in forward:
    visited[x].pop()
    return
  #print(forward[x])
  for y, p in forward[x].items():
    if y in visited and visited[y]:
      #print(y, p, 'visited')
      for q in visited[y]:
        if point+p > q:
    #      print(x, y, p, point, visited)
          print(-1)
          sys.exit()
      visited[x].pop()
      return
    else:
      #print(y, p, 'to_visit')
      visited[y] = visited.get(y, [])
      visited[y].append(point+p)
      dfs(y, point+p, visited)
  visited[x].pop()
  return
dfs(1, 0, {1: [0]})
#print(reached)
print(max(reached))

Buggy submission (verdict: Runtime Error):
import sys
N, M, P = [int(x) for x in input().split()]
forward = {}
backward = {}
for _ in range(M):
  A, B, C = [int(x) for x in input().split()]
  forward[A] = forward.get(A, {})
  if B in forward[A]:
    forward[A][B] = max(forward[A][B], C-P)
  else:
    forward[A][B] = C-P
  backward[B] = backward.get(B, {})
  if A in backward[B]:
    backward[B][A] = max(backward[B][A], C-P)
  else:
    backward[B][A] = C-P
#print(forward)
#print(backward)
reachable = set([N])
to_track = set([N])
while to_track:
  x = to_track.pop()
  if x not in backward:
    continue
  for y in backward[x]:
    if y not in reachable:
      to_track.add(y)
      reachable.add(y)
#print(reachable)
if 1 not in reachable:
  print(-1)
  sys.exit()

forward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
           for k, v in forward.items() if k in reachable}
#print(forward)
# backward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
#            for k, v in backward.items() if k in reachable}
#print(backward)


reached = [0]  # score is not negative
def dfs(x, point, visited):
  #print(x,point,visited)
  if x == N:
    reached.append(point)
  if x not in forward:
    visited[x].pop()
    return
  #print(forward[x])
  for y, p in forward[x].items():
    if y in visited and visited[y]:
      #print(y, p, 'visited')
      for q in visited[y]:
        if point+p > q:
    #      print(x, y, p, point, visited)
          print(-1)
          sys.exit()
      visited[x].pop()
      return
    else:
      #print(y, p, 'to_visit')
      visited[y] = visited.get(y, [])
      visited[y].append(point+p)
      dfs(y, point+p, visited)
dfs(1, 0, {1: [0]})
#print(reached)
print(max(reached))