Problem p03722 (python)

Fixed submission:


N,M = map(int, input().split())

from collections import defaultdict
neighbor = defaultdict(list)
Rneighbor = defaultdict(list)
edges = []
for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  edges += [(a,b,c)]
  neighbor[a].append(b)
  Rneighbor[b].append(a)

# only vertices that are reachable from 1 or N
v1 = set()
v1.add(0)
stack = [0]
while stack:
  v = stack.pop()
  for u in neighbor[v]:
    if u not in v1:
      v1.add(u)
      stack.append(u)

vn = set()
vn.add(N-1)
stack = [N-1]
while stack:
  v = stack.pop()
  for u in Rneighbor[v]:
    if u not in vn:
      vn.add(u)
      stack.append(u)

V = v1 & vn

edges = [(a,b,c) for a,b,c in edges if a in V and b in V]
score = [float('-inf')]*N
score[0] = 0

updated = True
i = 0

positive_cycle = False

while updated:
  if i == len(V):
    positive_cycle = True
    break

  updated = False
  for a,b,w in edges:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1

if positive_cycle:
  print('inf')
else:
  print(score[N-1])

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import depth_first_order,bellman_ford
import numpy as np
from time import process_time as timer

G = lil_matrix((N,N), dtype='i4')

for i in range(M):
  a,b,c = map(int, input().split())
  G[a-1,b-1] = -c

# remove nodes unreachable from goal or start
n1 = set(depth_first_order(G, 0, return_predecessors=False))
n2 = set(depth_first_order(G.T, N-1, return_predecessors=False))
n = n1&n2
# N = len(nodes)
# nodes.sort()
# G = G[np.ix_(nodes,nodes)]

try:
  dist = bellman_ford(G,list(n))
  print(-int(dist[0,N-1]))
except NegativeCycleError:
  print('inf')

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import *
import numpy as np
from time import process_time as timer

G = lil_matrix((N,N), dtype='i4')

for i in range(M):
  a,b,c = map(int, input().split())
  G[a-1,b-1] = -c

# remove nodes unreachable from goal or start
n1 = set(depth_first_order(G, 0, return_predecessors=False))
n2 = set(depth_first_order(G.T, N-1, return_predecessors=False))
n = n1&n2
# N = len(nodes)
# nodes.sort()
# G = G[np.ix_(nodes,nodes)]

try:
  dist = bellman_ford(G,list(n))
  print(-int(dist[0,N-1]))
except NegativeCycleError:
  print('inf')

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())

from collections import defaultdict
E = []

for i in range(M):
  a,b,c = map(int, input().split())
  a,b = a-1, b-1
  E += [(a,b,c)]

def reachable_vertices(neighbor, s):
  V = set()
  V.add(s)
  stack=[s]
  while stack:
    v = stack.pop()
    for u in neighbor[v]:
      if u not in V:
        V.add(u)
        stack.append(u)
  return V

def neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[a].append(b)
  return neighbor

def rev_neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[b].append(a)
  return neighbor

def degenerate_graph(V, E):
  d = {v:i for i,v in enumerate(sorted(V))}
  return len(V), [(d[a],d[b],c) for a,b,c in E]

# only vertices that are reachable from 1 or N
N,E = degenerate_graph(reachable_vertices(neighbor_dict(E), 0), E)
N,E = degenerate_graph(reachable_vertices(rev_neighbor_dict(E), N-1), E)
score = [float('-inf')]*N
score[0] = 0


i = 0
updated=True
while updated:
  if i == N:
    print('inf')
    break

  updated = False
  for a,b,w in E:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1
else:
  print(score[N-1])