Problem p03722 (python)

Fixed submission:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense, NegativeCycleError
import numpy as np

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1 and c != np.inf:
			g2[i][new[j]] = c

try:
	graph = csgraph_from_dense(g2, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[l-1])
	print(ans)

except NegativeCycleError:
	print("inf")

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense
import numpy as np

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1:
			g2[e][new[j]] = c


try:
	graph = csgraph_from_dense(g2, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
import numpy as np

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1:
			g2[e][new[j]] = c


try:
	graph = csr_matrix(g2)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")