Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

class BellmanFord():
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合
    
    @property
    def E(self):
        """ 辺数 """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)
    
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False

    

def main():
    mod=10**9+7
    N,M=MI()
    
    bf = BellmanFord()
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        bf.add(a,b,c*(-1))
        
    if bf.exist_negative_loop():
        print("inf")
    else:
        L=bf.shortest_path(0)
        print(-1*L[-1])

main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
paths = [list(map(int, input().split())) for _ in range(M)]

minimumScore = [-float('inf') for _ in range(N)]
minimumScore[0] = 0
count = 0
while count < N:
    flag = False
    for a, b, c in paths:
        if minimumScore[a-1] == -float('inf'):
            continue
        if minimumScore[a-1] + c > minimumScore[b-1]:
            minimumScore[b-1] = minimumScore[a-1] + c
            minimumScore[b-1] = minimumScore[a-1] + 1
            flag = True
    if not flag:
        break
    count += 1
tmp = minimumScore[-1]
for a, b, c in paths:
    if minimumScore[a-1] == -float('inf'):
        continue
    if minimumScore[a-1] + c > minimumScore[b-1]:
        minimumScore[b-1] = minimumScore[a-1] + c
        minimumScore[b-1] = minimumScore[a-1] + 1
        flag = True
if tmp != minimumScore[-1]:
    print('inf')
else:
    print(minimumScore[N-1][0])
#print(minimumScore[-1])

Submission status: Runtime Error

Solution code:
#Nは頂点数, Mは辺数(2 <= N <= 1000, 1 <= M <= min(N(N-1, 2000)))
#頂点1から頂点Nに移動して、移動スコアを最大にする
#->移動スコアを正負反転させれば最短経路問題
#->負閉路を考慮してベルマンフォード法を利用
INF = 1 << 50

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

#辺を登録
Sides = []
for i in range (M):
    Sides.append(map(int,input().split()))
#コストを反転
    Sides[i][2] = Sides[i][2] * (-1)

#各頂点の最短距離を初期化
Vertexes = [INF]*N+1
Vertexes[1] = [0]

#負閉路のチェック用
negative = [False] * N+1

#ベルマンフォード法による最短距離探索
for count in range(N):
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        cost = Sides[i][2]
        if (Vertexes[to_v] > Vertexes[from_v]+cost):
            if(count==N):
                negative[to_v] = True:
            Vertexes[to_v] = Vertexes[from_v]+cost

#負閉路の確認
for count in range(N-1):
    flag = 0
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        if negative[from_v] and negative[to_v] is False:
            negative[to_v] = True
            flag = 1
    if flag ==0:
        break

if negative[N]:
    print('inf')
else:
    print(Vertexes[N])

Submission status: Runtime Error

Solution code:
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

if flag:
  print('inf')
else:
  print(-dist[N-1])

Submission status: Runtime Error

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])

stack=[[1,0,set([1]),0,{1:0}]]#p,nagasa,visited,flag
ac=[]
while stack:
    p,m,miti,flag,dic=stack.pop()
    if not flag:
        for np,value in data[p]:
            if p in miti and m+value>dic[np]:
                flag=1
                if N in miti:
                    print("inf")
                    exit()
                break
    for np,value in data[p]:
        if np==N:

            if not flag:
                ac.append(m+value)
            else:
                print("inf")
                exit()
        if not np in miti:
            tempm=m+value
            tempmiti=copy.copy(miti)
            tempmiti.add(np)
            dic=copy.copy(dic)
            dic.update({np:tempm})
            stack.append([np,tempm,tempmiti,flag,dic])
print(max(ac))

Submission status: Runtime Error

Solution code:
INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

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

for j in range(N):
    for i in range(M):
        if d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]

for i in range(N):
    for j in range(M):
        if d[abc[i][0]] != INF and d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True

        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

if loop[N - 1]:
    print('inf')
else:
    print(ans)

Submission status: Runtime Error

Solution code:
INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

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

for j in range(N):
    for i in range(M):
        if d[abc[i][0]] != INF and d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]
for i in range(N):
    for j in range(M):
        if d[abc[i][0]] != INF and d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True
        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

if loop[N - 1]:
    print('inf')
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import scipy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m = map(int,input().split())
evv = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
  evv[i][2] = -evv[i][2]
  evv[i][0] -= 1
  evv[i][1] -= 1
v1,v2,edge = zip(*evv)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
try:
  print(-int(bellman_ford(csr, indices = 0)[n-1]))
except scipy.sparse.csgraph._shortest_path.NegativeCycleError:
  print("inf")

Submission status: Runtime Error

Solution code:
def BellmanFord(sv, ev, cv, num_v, source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i == n-1 and e == n-1:
          return "inf"
  
  return dist[-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))

Submission status: Runtime Error

Solution code:
def BellmanFord(sv, ev, cv, num_v, source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return "inf"
  
  return dist[num_v-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1)[N-1]*-1)

Submission status: Runtime Error

Solution code:
def BellmanFord(sv, ev, cv, num_v, source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return 1
  
  return dist

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1)[N-1]*-1)

Submission status: Runtime Error

Solution code:
def BellmanFord(sv, ev, cv, num_v, source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return -1
  
  return dist

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1)[N-1]*-1)

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[a - 1] is not None and \
                (distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c):
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[a - 1] is not None and
                (distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c):
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[a - 1] is not None and \
                distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[a - 1] is not None and distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve(n, m, ABC):
    g = [[] for _ in range(n)]
    for a, b, c in ABC:
        g[a - 1].append((b - 1, c))

    distance = [-10 ** 10] * n
    distance[0] = 0
    parents = [-1] * n
    ng = [False]

    def search(node):
        if ng[0]:
            return
        for to, d in g[node]:
            if node == parents[to] and distance[to] < distance[node] + d:
                ng[0] = True
                return
            if distance[to] < distance[node] + d:
                distance[to] = distance[node] + d
                parents[to] = node
            search(to)

    search(0)
    return 'inf' if ng[0] else distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Runtime Error

Solution code:
def solve():
    N,M = map(int, input().split())
    graph_cod = [[] for _ in range(N+1)]
    min_val = -1*(10**18)
    INF = 10**18
    for _ in range(M):
        a,b,c = map(int, input().split())
        graph_cod[b].append((a,c))
        
    ret = 0
    stack = [N]
    searched = [False]*(N+1)
    searched_nodes = []
    searched[N] = True
    
    distance = [min_val]*(N+1)
    distance[N] = 0
    # paths = [0]*(N+1)
    def dfs(cod, paths, depth):
        paths.append(cod)

        while graph_cod[cod]:
            dom, w = graph_cod[cod].pop()
            # print(cod, dom, distance, paths, depth)
            if searched[dom] and dom in paths:
                # 閉路探索
                while paths:
                    node = paths.pop()
                    distance[node] = INF
                    if node == dom:break
                    
            searched[dom] = True
            distance[dom] = max(distance[dom], distance[cod]+w)
            
            dfs(dom, paths, depth+1)
            paths = paths[:depth]
            # paths = copy(paths)
            
    dfs(N, [], 0)
            
    ret = distance[1] if distance[1] < INF else 'inf'
    
    print(ret)
    
solve()

Submission status: Runtime Error

Solution code:
from math import ceil,log2

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {}
    for v,w,c in VWC:
        if v not in changeable:
            changeable[v] = True
        if w not in changeable:
            changeable[w] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = Ans.copy()
    for _ in range(2*(node_num-1)):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#ABC061D - Score Attack
#https://atcoder.jp/contests/abc061/tasks/abc061_d
#自己考察

import sys
n, m = list(map(int,input().split()))
lst = [[] for _ in range(n+1)]#*(n+1)の挙動がよくわからない
for i in range(n):
    a, b, c = list(map(int,input().split()))
    lst[a].append((b,-c))
dp = [float("Inf")]*(n+1)
dp[1] = 0

for _ in range(n):
    for f in range(1,n+1):
        if dp[f] != float("Inf"):
            for t, c in lst[f]:
                dp[t] = min(dp[t], dp[f] + c)

for f in range(1,n+1):
    for t,c in lst[f]:
        if dp[t] > dp[f] + c:
            print("inf")
            sys.exit()

print(-dp[n])

Submission status: Runtime Error

Solution code:
def shortest_path(s,n,w,es):
#s→iの最短距離
# s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float('inf')] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    while True:
        update = False
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
            if not update:
                print(1)
                break
            ans1=d[-1]
        update = False
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True

            ans2=d[-1]
        return -ans1 if ans1==ans2 else 'inf' 
################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]
for _ in range(w):
 x,y,z = map(int,input().split())
 es.append([x-1,y-1,-z])
print(shortest_path(0,n,w,es))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u, s=0):
        if route[u]:
            if s>score[u]:
                return True
            return False
        route[u]=True
        score[u]=max(score[u],s)
        for v,c in to[u]:
            if dfs(v,s+c):return True
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    to = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        to[a].append([b, c])
        ot[b].append([a, c])

    score = [-inf] * n
    route=[False]*n
    if dfs(0):
        print("inf")
    else:
        print(score[n-1])

main()

Submission status: Runtime Error

Solution code:
INF = float('inf')
def bellmanford(n, edges, r):  # r : start
    d = [INF] * n
    d[r] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    return d[n-1]


N, M = map(int, input().split())
edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)
ans = bellmanford(N, edges, 0)
print(-ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    ans = res[N-1]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    if ans != res[N-1]
        # あったら空リストを返却
        return []
    # 問題なければ頂点リストを返却
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

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

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph import connected_components

N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in range(N)]

row, col, val = zip(*ABC)
# -1倍しておいて最短路問題にする
val = [-(x) for x in val]
graph = csr_matrix((val,(row,col)),(N+1,N+1))

# 強連結成分に制限。ここに負閉路があればinf～
find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
# n = 個数、label=各頂点が属する連結成分のラベル[0,0,1,1,1]
n, labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1]) # [False, False, True~]
graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Runtime Error

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n] == src and pre[src] == n:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

Submission status: Runtime Error

Solution code:
# coding:utf-8
from pprint import pprint

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    ##### 前処理 #####
    from collections import defaultdict
    # INFの定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####

    is_cycle = False

    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)




n, m = map(int, input().split(' '))
# 辺の情報
e = []
for _ in range(m):
    a, b, c = map(int, input().split(' '))
    e.append((a, b, -c))


dist, pre, is_cycle = bellman_ford(n, e, 1)

'''
print()
print('##### GRAPH2 (負の閉路あり) #####')
print()
print('===== dist =====')
pprint(dist)
print()
print('===== pre =====')
pprint(pre)
print()
print('===== is_cycle =====')
print(is_cycle)
print('#################################')
print()
'''



if is_cycle:
    g = n
    for i in range(len(pre)):
        g = pre[g]

    if g == 1:
        print(-dist[n])
    else:
        print('inf')

else:
    print(-dist[n])