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: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph=[[] for i in range(N+1)]
for _ in range(M):
    a,b,weight=map(int,input().split())
    graph[a].append((b,-weight))
    
class Node():
    def __init__(self,name):
        self.name=name
        self.par=None
        self.d=float("inf")
        
    def relax(self,other,weight):
        if self.d>other.d+weight:
            self.d=other.d+weight
            self.par=other.name
            
def bellman_ford(graph,s_node):
    N=len(graph)-1
    d_list=[Node(i) for i in range(N+1)]
    #初期化
    d_list[s_node].d=0
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)           
    for  node in range(1,N+1):
        for tuple_ in graph[node]:
            point,distance=tuple_
            if d_list[point].d>d_list[node].d+distance:
                return False
    return d_list  

K=bellman_ford(graph,1)
if K!=False:
    print(-K[N].d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
'''
ベルマンフォード法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
負の辺が使われている場合に使う。

O(|E||V|)
'''
class BellmanFord():
    def __init__(self, N):
        '''
        Parameters
        ----------
        N:int
            the number of nodes
        '''
        self.N = N
        self.edges = []
    
    def add(self, u, v, d, directed=False):
        '''
        Parameters
        ----------
        u:int
            from node (not 0-index)
        v:int
            to node (not 0-index)
        d:int
            cost
        directed:bool
            there is direction
        '''
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def calc(self, s):
        '''
        Parameters
        ----------
        s:int
            start index (not 0-index)
        
        Returns
        ----------
        list or bool
            d[i] is shortest distances from node[s] to node[i]
            if there is negative loop, return False
        '''
        dist = [float('inf') for i in range(self.N)]
        dist[s-1] = 0
        #辺の緩和
        for i in range(self.N):
            for edge in self.edges:
                if edge[0] != float('inf') and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                    dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                    if i==self.N-1: return -float('inf')
        return dist[-1]

'''
ABC061-D
N頂点M辺の重み付き有向グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
その辺を移動したときスコアc_iが加算される。
頂点1から始まり、頂点Nに駒があるときゲームを終了できる。
頂点1からNまで移動できることは保証されている。
ゲーム終了時のスコアを最大にするような行動をとった時の最大スコアを出力せよ。
スコアが無限に大きくなる場合はinfを出力せよ。

term:
2<=N<=1000
1<=M<=min(N(N-1),2000)
1<=a_i,b_i<=N
-10**9<=c_i<=10**9

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

output:
    7
'''

from collections import defaultdict,deque
import sys, bisect, math, itertools, heapq
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
graph=BellmanFord(n)
for _ in range(m):
    a, b, c = inpl()
    graph.add(a, b, -c, directed=True)  #\sum c_iを最大化する
result = graph.calc(1)
if result!=-float('inf'):
    print(-result)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
'''
ベルマンフォード法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
負の辺が使われている場合に使う。

O(|E||V|)
'''
class BellmanFord():
    def __init__(self, N):
        '''
        Parameters
        ----------
        N:int
            the number of nodes
        '''
        self.N = N
        self.edges = []
    
    def add(self, u, v, d, directed=False):
        '''
        Parameters
        ----------
        u:int
            from node (not 0-index)
        v:int
            to node (not 0-index)
        d:int
            cost
        directed:bool
            there is direction
        '''
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def calc(self, s):
        '''
        Parameters
        ----------
        s:int
            start index (not 0-index)
        
        Returns
        ----------
        list or bool
            d[i] is shortest distances from node[s] to node[i]
            if there is negative loop, return False
        '''
        dist = [float('inf') for i in range(self.N)]
        dist[s-1] = 0
        #辺の緩和
        for i in range(self.N):
            for edge in self.edges:
                if edge[0] != float('inf') and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                    dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                    if i==self.N-1: return False
        return dist

'''
ABC061-D
N頂点M辺の重み付き有向グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
その辺を移動したときスコアc_iが加算される。
頂点1から始まり、頂点Nに駒があるときゲームを終了できる。
頂点1からNまで移動できることは保証されている。
ゲーム終了時のスコアを最大にするような行動をとった時の最大スコアを出力せよ。
スコアが無限に大きくなる場合はinfを出力せよ。

term:
2<=N<=1000
1<=M<=min(N(N-1),2000)
1<=a_i,b_i<=N
-10**9<=c_i<=10**9

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

output:
    7
'''

from collections import defaultdict,deque
import sys, bisect, math, itertools, heapq
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
graph=BellmanFord(n)
for _ in range(m):
    a, b, c = inpl()
    graph.add(a, b, -c, directed=True)  #\sum c_iを最大化する
result = graph.calc(1)
if result:
    print(-result[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
'''
ベルマンフォード法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
負の辺が使われている場合に使う。

O(|E||V|)
'''
class BellmanFord():
    def __init__(self, N):
        '''
        Parameters
        ----------
        N:int
            the number of nodes
        '''
        self.N = N
        self.edges = []
    
    def add(self, u, v, d, directed=False):
        '''
        Parameters
        ----------
        u:int
            from node (not 0-index)
        v:int
            to node (not 0-index)
        d:int
            cost
        directed:bool
            there is direction
        '''
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def calc(self, s):
        '''
        Parameters
        ----------
        s:int
            start index (not 0-index)
        
        Returns
        ----------
        list or bool
            d[i] is shortest distances from node[s] to node[i]
            if there is negative loop, return False
        '''
        dist = [float('inf') for i in range(self.N)]
        dist[s-1] = 0
        num_v=len(self.edges)
        #辺の緩和
        for i in range(num_v):
            for edge in self.edges:
                if edge[0] != float('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: return False
        return dist

'''
ABC061-D
N頂点M辺の重み付き有向グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
その辺を移動したときスコアc_iが加算される。
頂点1から始まり、頂点Nに駒があるときゲームを終了できる。
頂点1からNまで移動できることは保証されている。
ゲーム終了時のスコアを最大にするような行動をとった時の最大スコアを出力せよ。
スコアが無限に大きくなる場合はinfを出力せよ。

term:
2<=N<=1000
1<=M<=min(N(N-1),2000)
1<=a_i,b_i<=N
-10**9<=c_i<=10**9

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

output:
    7
'''

from collections import defaultdict,deque
import sys, bisect, math, itertools, heapq
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
graph=BellmanFord(n)
for _ in range(m):
    a, b, c = inpl()
    graph.add(a, b, -c, directed=True)  #\sum c_iを最大化する
result = graph.calc(1)
if result:
    print(-result[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
check=[False for i in range(n+1)]
inf=False
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      check[e]=True
if check[n]:
  inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
if inf:
  print('inf')
else:
  for i in range(n-1):
    for s,e,c in edge:
      if node[e]>node[s]+c:
        node[e]=node[s]+c
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
check=[False for i in range(n+1)]
inf=False
for i in range(n):
  loop=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      if check[e]:
        loop=True
      check[e]=True
  if loop:
    inf=True
    break
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n-1):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
check=[False for i in range(n+1)]
inf=False
for i in range(n):
  loop=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      if check[e]:
        loop=True
      check[e]=True
  if loop and check[n]:
    inf=True
    break
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n-1):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
check=[False for i in range(n+1)]
inf=False
for i in range(n):
  change=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      if check[e]:
        change=True
      check[e]=True
  if change and check[n]:
    inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
inf=False
for i in range(n):
  change=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      if e==n:
        change=True
  if change:
    inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
inf=False
for i in range(n):
  change=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      change=True
  if i==n-1 and change:
    inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
inf=False
for i in range(n):
  change=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      change=True
  if i==n and change:
    inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
node=[0 for i in range(n+1)]
inf=False
for i in range(n+1):
  change=False
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      change=True
  if i==n and change:
    inf=True
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
if inf:
  print('inf')
else:
  print(-node[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
node=[-float('inf') for i in range(n+1)]
node[1]=0
inf=False
for i in range(n+1):
  change=False
  for s,e,c in edge:
    if node[e]<node[s]+c:
      node[e]=node[s]+c
      change=True
  if i==n and change:
    inf=True
if inf:
  print('inf')
else:
  print(node[-1])

Submission status: Wrong Answer

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:        
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    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: Wrong Answer

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:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    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: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if update and cnt == m: return 'inf'
        cnt += 1
    return d[n]

print(shortest_path(1))

Submission status: Wrong Answer

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 a,b,c in abc:
    a,b = a-1,b-1
    es.append((a,b,c))

INF = float('inf')

def find_negative_loop(n,es,s):
    #負の経路の検出
    #n:頂点数, es[i]: [辺の始点,辺の終点,辺のコスト], s:始点
    dist = [-INF] * n
    dist[s] = 0

    for i in range(n):
        for a,b,c in es:
            if dist[b] < dist[a]+c:
                dist[b] = dist[a]+c
                if i == n-1: # n回目にも更新が行われている場合，ループが存在する
                    return INF
    return dist[n-1]

ans = find_negative_loop(n,es,0)

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

print(ans)

Submission status: Wrong Answer

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(m)]
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: Wrong Answer

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: Wrong Answer

Solution code:
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:
            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]
                #dist[edge[0]-1] = dist[edge[1]-1] - edge[2]
                if i==num_v-1: return -1

    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)

if (res == -1 )or (res==float("inf")):
    print("inf")
else:
    print(-res[-1])

Submission status: Wrong Answer

Solution code:
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:
            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]
                #dist[edge[0]-1] = dist[edge[1]-1] - edge[2]
                if i==num_v-1: return -1

    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)
if res == -1:
    print("inf")
else:
    print(-res[-1])

Submission status: Wrong Answer

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())

L = np.zeros((n,n),dtype = np.int32)
for _ in range(m):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = -c

try:
    dist = bellman_ford(csr_matrix(L),indices=[0]).astype(np.int64)
    ans = -dist.reshape(-1)[-1]
except:
    ans = "inf"
print(ans)

Submission status: Wrong Answer

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())

L = np.zeros((n,n),dtype = np.int32)
for _ in range(m):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = -c

try:
    dist = bellman_ford(csr_matrix(L),indices=0).astype(np.int64)
    ans = -dist[-1]
except:
    ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def bellman_ford(edges, N, start):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0
    # 辺の情報を見ることを1ループとすると
    # 1回のループで,最低でも1つの頂点について，スタートからの最短距離が求まる
    # つまり,スタートからの全ての頂点への距離は，
    # スタートを除いた頂点の数である,(N-1)回のループで求まる．
    for i in range(N):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] - cost:
                dist[to] = dist[fro] - cost
                # N回目に頂点の更新があると，負の経路がある
                if i == N - 1:
                    dist[to] = float("inf")
    return dist


def main():
    N, M = map(int, input().split())
    edge = []
    for i in range(M):
        a, b, c = map(int, input().split())
        edge.append((a - 1, b - 1, c))
    D = bellman_ford(edge, N, 0)
    if D[-1] == float("inf"):
        print(D[-1])
    else:
        print(-1 * D[-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    # Weight Maximization
    MIN_INF = - 10**15
    d = [MIN_INF for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] < new_d:
                d[edge.to_node] = new_d
                updated = True
        if not updated:
            return d[goal]
        if loop == N - 1:
            # exists a positive loop
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = c
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    # Weight Maximization
    MIN_INF = - 1e+15
    d = [MIN_INF for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] < new_d:
                d[edge.to_node] = new_d
                updated = True
        if not updated:
            print(d[start], d[goal])
            return d[goal]
        if loop == N - 1:
            print(d[start], d[goal])
            # exists a positive loop
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = c
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    # Weight Maximization
    MIN_INF = - 10**13
    d = [MIN_INF for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] < new_d:
                d[edge.to_node] = new_d
                updated = True
        if not updated:
            print(d[start], d[goal])
            return d[goal]
        if loop == N - 1:
            print(d[start], d[goal])
            # exists a positive loop
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = c
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    L = 10**15  # large number
    d = [L for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] > new_d:
                d[edge.to_node] = new_d
                updated = True
        if not updated:
            return d[goal]
        if loop == N - 1:
            # exists a negative loop
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = - c  # multiply (-1) to change maximization to minimization
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print((-1) * result)

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    L = 10**12  # large number
    d = [L for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] > new_d:
                d[edge.to_node] = new_d
                updated = True
        if not updated:
            return d[goal]
        if loop == N - 1:
            # exists a negative loop
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = - c  # multiply (-1) to change maximization to minimization
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print((-1) * result)


if __name__ == '__main__':
    main()