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:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
N,M = map(int,input().split())
start = []
goal = []
data1 = []
data2 = []
for _ in range(M):
    a,b,c = map(int,input().split())
    start.append(a)
    goal.append(b)
    data1.append(c)
    data2.append(-c)
csr1 = csr_matrix((data1,(start,goal)),shape=(N+1,N+1))
csr2 = csr_matrix((data2,(start,goal)),shape=(N+1,N+1))
try:
    p = shortest_path(csr1)
    q = shortest_path(csr2)
    if np.min(p)<np.min(q):
        print(int(np.min(p)))
    else:
        print(-int(np.min(q))
except:
    print("inf")

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


def bellman_ford(edges, num_v, sv):
    #グラフの初期化
    dist = [INF] * num_v
    dist[sv]=0
    
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] != INF and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
                if i == num_v - 1:
                    return -1       # 負の閉路が存在する
    
    return dist


def main():
    N, M = map(int, input().split())

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

    if dist == 0:
        print("inf")
    else:
        print(-dist[N-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

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

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1,N):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Runtime Error

Solution code:
N,M,*L = map(int, open('0').read().split())
dic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append(b)

ok = [False]*(N+1)
ok[1] = True
q = [1]
while q:
  p = q.pop()
  for v in dic[p]:
    if not ok[v]:
      ok[v] = True
      q.append(v)
cnt = 0
dist = [-10**20]*(N+1)
dist[1] = 0
while True:
  flag = True
  for a,b,c in zip(*[iter(L)]*3):
    if ok[a]&ok[b] and ok[a]!=-10**20 and dist[b]<dist[a]+c:
      flag = False
      dist[b] = dist[a]+c
  if flag:
    print(dist[N])
    break
  cnt += 1
  if cnt>N:
    print('inf')
    break

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N-1):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
    negative = ['false'] * len(N)

    for i in range(N):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                negative[edge[1] - 1] = True
            if negative[edge[0] - 1] == True:
                negative[edge[1] - 1] =True

    return 'inf' if negative[-1] else -dist[-1]

print(bellman_ford(edges, N))

Submission status: Runtime Error

Solution code:
"""
お借りしました.
https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
"""

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

INF = 10**18
dist = [INF] * V
dist[0] = 0
update = 1
for _ in range(V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
    print("inf")
    exit()

print(-dist[-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[False*(N+1)]
for i in range(1,N+1):
  if not reachable[i]:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  res=check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[a] and reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  res=check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  res=check_reachable(i,i)
#print(reachable_list)
  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())

abc = [tuple(map(int,input().split())) for i in range(m)]
es = [[] for i in range(n)]
for i,(a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    es[i]=[a,b,c]

INF = float('inf')

#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [-INF] * n
    d[0] = 0
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] < d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return INF
    return d[n-1]

ans = find_negative_loop(n,m,es)

if ans == INF:
    print('inf')
    exit()

print(ans)

Submission status: Runtime Error

Solution code:
import sys
def BellmanFord(edges,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 edge in edges:
            #print(dist)
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: 
                	print("inf")
                    sys.exit()

    return dist

n,m=map(int,input().split())
es=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    es.append((a,b,-c))
    
res=BellmanFord(es,n,1)
print(-res[-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(2N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-1:
      t = score[N-1]
    if i == 2N:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import copy

n,m = na()
g = [[] for i in range(n)]

for i in range(m):
    a,b,c = na()
    a,b = a-1,b-1
    g[a].append((b,c))

def dfs(k, rr, ss):
    s = copy.copy(ss)
    ans = -1000000000000
    for v,c in g[k]:
        r = rr+c
        if v == k:
            if c > 0:
                print('inf')
                exit()
            continue
        if v in s:
            if r > s[v]:
                print('inf')
                exit()
            else:
                return
        s[v] = r
        ans = max(ans,dfs(v,r,s))
        if v == n-1:
            ans = max(ans, r)
    return ans

print(dfs(0, 0, {}))

Submission status: Runtime Error

Solution code:
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self,gorl):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[gorl]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans if self.ans == self.dist[gorl] else '-inf'

n,m = map(int,input().split())

bf = BellmanFord(n,0)

for i in range(m):
    a,b,c = map(int,input().split())
    bf.add(a - 1,b - 1,- c)

ans = bf.build()
if ans == '-inf':
    print('inf')
else:
    print(- ans)

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[es[0]] or negative[es[1]]:
        negative[es[0]] = 1
        negative[es[1]] = 1
if negative[N]:
    print('inf')
else:
    print(d[N])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
x=[list(map(int,input().split())) for i in range(m)]
dp=[0 for i in range(n+1)]
import sys
# for i in range(m):
#     if x[i][0]:
#         print('inf')
#         sys.exit()
for i in range(2,n+1):
    ans=[]
    for k in range(m):
        if x[k][1]==i:
            if x[k][1]<=x[k][0]:
                print('inf')
                sys.exit()
            else:
                ans.append(dp[x[k][0]]+x[k][2])
    print(ans)
    dp[i]=max(ans)
print(dp[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
x=[list(map(int,input().split())) for i in range(m)]
dp=[0 for i in range(n+1)]
import sys
for i in range(m):
    if x[i][0]==n:
        print('inf')
        sys.exit()
for i in range(2,n+1):
    ans=[]
    for k in range(m):
        if x[k][1]==i:
            ans.append(dp[x[k][0]]+x[k][2])
    print(ans)
    dp[i]=max(ans)
print(dp[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
x=[list(map(int,input().split())) for i in range(m)]
dp=[0 for i in range(n+1)]
import sys
for i in range(m):
    if x[i][0]==n:
        print('inf')
        sys.exit()
for i in range(2,n+1):
    ans=[]
    for k in range(m):
        if x[k][1]==i:
            ans.append(dp[x[k][0]]+x[k][2])
    # print(ans)
    dp[i]=max(ans)
print(dp[n])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
V=[False]*N
G=[[False for _ in range(N)] for _ in range(N)]
W=[[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G[a-1][b-1]=True
  G[b-1][a-1]=True
  W[a-1][b-1]=c
  W[b-1][a-1]=c
flg=False
ans=0
def dfs(v,w):
  global ans, flg
  if v==N-1:
    flg=True
    ans=max(ans,w)
    return
  for i in range(N):
    if i==v or V[i] or G[v][i]==False: continue
    V[i]=True
    dfs(i,w+W[v][i])
    V[i]=False
V[0]=True
dfs(0,0)
if flg: print(ans)
else: print("inf")

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

n, m = map(int, input().split())
GRAPH = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    GRAPH[a][b] = -c

try:
    sp = bellman_ford(csgraph_from_dense(GRAPH), indices=0)
except NegativeCycleError:
    print('inf')
else:
    print(-int(sp[-1]))

Submission status: Runtime Error

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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


#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
                if i == n-1:
                    return 0
    return d


#############################
ans=find_negative_loop(n,m,abcimport sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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


#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n-1):
        for j in range(w):
            e = es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
    neg=[False]*n
    for i in range(n):
        for j in range(w):
            e=es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
                neg[e[1]-1]=True
            if neg[e[0]-1]==True:
                neg[e[1]-1]=True
    return (d,neg)


#############################
ans=find_negative_loop(n,m,abc)
if ans[1][-1]==True:
    print("inf")
else:
    print(-ans[0][-1])
if ans==0:
    print("inf")
else:
    print(-ans[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + ['inf']*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][1]-1] == 'inf' or point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1) and a[i][1]-1 == (n-1):
        point.append('inf')
        
        
if 'inf' in point:
  print('inf')
else:
  print(-point[n-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + ['inf']*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][1]-1] == 'inf' or point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1):
        point.append('inf')
        
        
if 'inf' in point:
  print('inf')
else:
  print(-point[n-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + ['inf']*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][1]-1] == 'inf' or point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1):
        point.append('inf')
        
        
if 'inf' in point:
  print('inf')
else:
  print(-point[n-1])

Submission status: Runtime Error

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        neg = [False for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] == INF:continue
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    neg[v] = True
                    if i == V-1:return True
                if neg[u]:
                    neg[v] = True 
        return neg

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    neg = bf.findneg(N,E)
    if neg[-1]:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        neg = [False for _ in range(N)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] == INF:continue
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    neg[v] = True
                    if i == V-1:return True
                if neg[u]:
                    neg[v] = True 
        return neg

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    neg = bf.findneg(N,E)
    if neg[-1]:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n+1)
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
            if z == n:
                print('inf')
                exit()
print(-dis[n-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        a -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
    if not update:
        break

if z == n:
    print('inf')
else:
    print(-dis[n-1])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
link = []
for i in range(m):
    tmp = list(map(int,input().split()))
    link.append([tmp[0]-1,tmp[1]-1,-tmp[2]])

def bell(edges, start,num_v):
    cost = [float('inf')] * num_v
    cost[start] = 0
    for _ in range(num_v):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return -1,cost
    return 1,cost

ans1,d = bell(link,0,n)

if ans1 == -1:
    inf_flag = [False]*n
    for i in range(n):
        for f, t, c in link:
            if d[f] == float("inf"): continue
            if inf_flag[f] == True:
                inf_flag[t] = True
            if d[t] > d[f] + c:
                d[t] = d[f] + c
                inf_flag[t] = True
    print("inf" if inf_flag[n-1] else -d[n-1])
else:
    print(-ans2[-1])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
link = []
for i in range(m):
    tmp = list(map(int,input().split()))
    link.append([tmp[0]-1,tmp[1]-1,-tmp[2]])

def bell(edges, start,num_v):
    cost = [float('inf')] * num_v
    cost[start] = 0
    for _ in range(num_v):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return -1,cost
    return 1,cost

ans1,ans2 = bell(link,0,n)

if ans1 == -1:
    inf_flag = [False]*N
    for i in range(N):
        for f, t, c in v:
            if d[f] == inf: continue
            if inf_flag[f] == True:
                inf_flag[t] = True
            if d[t] > d[f] + c:
                d[t] = d[f] + c
                inf_flag[t] = True
    print("inf" if inf_flag[N-1] else -d[N-1])
else:
    print(-ans2[-1])

Submission status: Runtime Error

Solution code:
V, E = map(int, input().split())
G = [[] for i in range(V+1)]
for i in range(E):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, 0-c))
G[V-1].append((V, 0))

INF = float('inf')
dist = [INF] * (V + 1)
dist[0] = 0
Flag = False

for i in range(V+1):
    UnUpdate = True
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                UnUpdate = False
    if UnUpdate and i < V:
        Flag = True
        break

if Flag:
    print(0-dist[V])
else:
    print(1/0)