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

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,-c])

def bellman_ford(g,n):
    INF = 10**15
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            for sa,sb in g[i]:
                res[sa] = min(res[sa],res[i]+sb)
    f = [False for _ in range(n)]
    for _ in range(n+1):
        for i in range(n):
            for sa,sb in g[i]:
                if res[sa] > res[i]+sb:
                    res[sa] = res[i]+sb
                    f[sa] = True
    if f[-1]: return "inf"
    else:return res[-1]*-1

print(bellman_ford(g,n))

Solution (Python):
inf=1e13

def bellmanford(E,N):
    score=[inf for i in range(N)]
    score[0]=0
    for i in range(N-1):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])
    temp=score[N-1]
    score = [inf for i in range(N)]
    score[0] = 0
    for i in range(N):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])
    loop=(temp!=score[N-1])

    return temp,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    E=[list(map(int, input().split())) for _ in range(M)]
    negative_E=[]
    for a,b,c in E:
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(negative_E,N)
    if loop:
        print("inf")
    else:
        print(-score)

Solution (Python):
import sys
 
inf = float('inf')
 
n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))
 
def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)
 
    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf
 
    return -dist[n-1]
 
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
 
inf = float('inf')
 
n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))
 
def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)
 
    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf
 
    return -dist[n-1]
 
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf

    return -dist[n-1]

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
a = []
b = []
c = []
for _ in range(m):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    a.append(ai - 1)
    b.append(bi - 1)
    c.append(-ci)
abc = list(zip(a, b, c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    res = dist[n-1]

    for _ in range(n):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    if dist[n-1] == res:
        return -res
    else:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

INF = 10 ** 15

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = list(zip(*[abc] * 3))

def main():
    dist = [INF] * n
    dist[0] = 0
    for _ in range(n - 1):
        for a, b, c in abc:
            a -= 1; b -= 1; c = -c
            if dist[a] == INF:
                continue
            dist[b] = min(dist[b], dist[a] + c)

    res = dist[n-1]

    for _ in range(n - 1):
        for a, b, c in abc:
            a -= 1; b -= 1; c = -c
            if dist[a] == INF:
                continue
            dist[b] = min(dist[b], dist[a] + c)

    if dist[n-1] == res:
        return -res
    else:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    
    
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    
    for i in range(num_v):
        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:
                    
                    neg_flg=True
                neg[v] = True
    if neg_flg:
        for i in range(num_v):
            for u,v,d in edges:
                if dist[v] > dist[u] + d:
                    dist[v] = dist[u] + d
    if dist[n-1]==check:
        neg_flg=False
    return neg_flg,dist
 

show_flg=False
show_flg=True

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

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

fl,d=BellmanFord(g,n,0)
if fl:
    ans='inf'
else:
    ans=-d[n-1]
print(ans)

Solution (Python):

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 = 2**63 - 1
    
    dist = defaultdict(lambda: INF) 
    dist[s] = 0
    
    pre = {}

    
    
    for i in range(V-1):
        for n1, n2, w in E:
            
            
            
            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:
        
        
        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('
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(n-1):
        g = pre[g]
        if g == 1:
            break

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

else:
    print(-dist[n])

Solution (Python):


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

    
    
    for i in range(V-1):
        for n1, n2, w in E:
            
            
            
            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:
        
        
        if dist[n1] + w > dist[n2]:
            is_cycle = True

    is_cycle = checkpath(pre, V, s)
            
    return (dist, pre, is_cycle)


def checkpath(pre, N, s):
    if s in pre and pre[N] == s and pre[s] == N:
        return True
    count = 0
    p = pre[N]
    while p != s:
        p = pre[p]
        
        if p == s and s in pre:
            return True
        count += 1
        if count >= N-1:
            return True
    return False

def main():
    
    N, M = map(int, input().split(' '))
    
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, c))
    
    s = 1

    
    dist, pre, is_cycle = bellman_ford(N, E, s)

    
    
    
    
    if is_cycle:
        print("inf")
    else:
        print(dist[N])



if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
ABC = []
for i in range(M):
  a,b,c=map(int,input().split())
  c=-c
  ABC.append([a,b,c])

def BellmanFord():
  inf=float("Inf")
  dist=[inf for i in range(N)]
  dist[0]=0
  
  for i in range(N):
    for edge in ABC:
      if dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==N-1 and edge[1]-1==N-1: return inf
    
  return -dist[N-1]
  
print(BellmanFord())

Solution (Python):

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 = 2**63 - 1
    
    dist = defaultdict(lambda: INF) 
    dist[s] = 0
    
    pre = {}

    
    
    for i in range(V-1):
        for n1, n2, w in E:
            
            
            
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    
    is_cycle = False
    cycle_node = []
    for n1, n2, w in E:
        
        
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            cycle_node.append(n1)

    
    is_inf = False
    if is_cycle:
        route_node = V
        while route_node != s:
            route_node = pre[route_node]
            if route_node in cycle_node:
                is_inf = True
                break

    return 'inf' if is_inf else str(-dist[V])


def main():
    
    N, M = map(int, input().split(' '))
    
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    print(bellman_ford(N, E, 1))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

INF = float('inf')

def Bellmanford(n, edges, r): 
    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, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)

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

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    k = 0
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
                    if k == N-1 and j == N-1: return (1, [])
        k += 1
        if k == N: return (0, D)
    return (0, D)

b, d = bellman_ford(N, E1)
if b:
    print("inf")
else:
    print(-d[-1])

Solution (Python):
from collections import deque
N, M = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E1[a-1].append((b-1, -c))
    E2[b-1].append((a-1, -c))

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c, w in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    while f:
        f = 0
        for i in range(n):
            if not B[i]: continue
            for j, c in E[i]:
                if not B[j]: continue
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
    return D

def bellman_ford_check(n, E, s=0):
    D = [0] * n
    for k in range(n):
        for i in range(n):
            if not B[i]: continue
            for j, c in E[i]:
                if not B[j]: continue
                if D[j] > D[i] + c:
                    D[j] = D[i] + c
                    if k == n-1: return 1
    return 0

B1 = BFS(N, E1, 0)
B2 = BFS(N, E2, N-1)
B = [0 if B1[i] < 0 or B2[i] < 0 else 1 for i in range(N)]

if bellman_ford_check(N, E1):
    print("inf")
else:
    D = bellman_ford(N, E1)
    print(-D[-1])

Solution (Python):
INF = 10 ** 15


def bellman_ford(v, G):
    ret = [INF] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    for _ in range(len(G)):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = -INF

    return ret


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

ans = bellman_ford(0, G)[-1]
print('inf' if ans == -INF else -ans)

Solution (Python):

import sys

def BellmanFord(graph: "List[List[int]]", s: int):
    """
    特定の始点から各点への最短距離を求めます。
    重みが負であっても動作します。
    ================
    s: 始点
    graph: 隣接リスト
    ----------------
    第一返り値: 負の閉路があるかいなか
    第二返り値: 最短距離のリスト
    """
    INF = 1e18
    n = len(graph)
    dist = [INF] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(graph[v])):
                e  = graph[v][k]
                if dist[v] != INF and dist[e[0]] > dist[v] + e[1]:
                    dist[e[0]] = dist[v] + e[1]
                    if i == n-1 and e[0] == n-1:
                        return True, dist
    return False, dist

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(M):
        G[a[i]-1].append((b[i]-1, c[i]))
    flag, cost = BellmanFord(G, 0)
    if flag:
        print('inf')
    else:
        print(-cost[N-1])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    c = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = -1 * int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    for k in e.keys():
      for t in e[k]:
        self.edges.append((k, t[0], t[1]))
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    for i in range(self.n + 1):
      for (u, v, c) in self.edges:
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i == self.n and (v == self.n):
            return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path(1, N)
if res == "-loop": print("inf")
else: print(-res)

Solution (Python):
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M= map(int, input().split())
P = 0
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = float("inf")
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print("inf")
          exit(0)
dfs(1)
print(earn[N])

Solution (Python):
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            if i == n - 1 and _to == n-1:
                flg = True
if flg:
    print("inf")
else:
    print(d[-1])

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10**17

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


def bfs(graph, start):
    checked = [False]*N
    checked[start] = True
    q = [start]
    while q:
        qq = []
        for p in q:
            for np in graph[p]:
                if not checked[np]:
                    qq.append(np)
                    checked[np] = True
        q = qq
    return checked

graph1 = [[] for _ in range(N)]
graph2 = [[] for _ in range(N)]
for a, b, e in Edges:
    graph1[a-1].append(b-1)
    graph2[b-1].append(a-1)

checked1 = bfs(graph1, 0)
checked2 = bfs(graph2, N-1)

n_Edges = []
for a, b, e in Edges:
    if checked1[a-1] and checked2[b-1]:
        n_Edges.append((a, b, e))

D = [INF]*N
D[0] = 0
ok = True
for i in range(N):
    update = False
    for a, b, c in n_Edges:
        if D[a-1] != INF and D[b-1] > D[a-1] - c:
            D[b-1] = D[a-1] - c
            update = True
    if i==N-1 and update:
        ok = False

if not ok:
    print('inf')
else:
    print(-D[N-1])

Solution (Python):
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for i in range(M)]
cost = [-float("inf")] * N
cost[0] = 0

for n in range(N-1):
  for m in range(M):
    a, b, c = edge[m]
    cost[b-1] = max(cost[b-1], cost[a-1] + c)

r = cost[-1]
for m in range(M):
    a, b, c = edge[m]
    cost[b-1] = max(cost[b-1], cost[a-1] + c)

print(r if cost[-1] == r else "inf")

Solution (Python):
def find_negative_loop(n, w, edges):
    d = [float('inf')] * n
    d[0] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                if i == n - 1 and v == n - 1:
                    return None
    return d[n-1]

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


    ans = find_negative_loop(N, M, edges)

    if ans:
        print(-1 * ans)
    else:
        print('inf')

    
    

if __name__ == "__main__":
    main()

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

INF = 10 ** 13
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')

Solution (Python):
inf = float('inf')

def solve():
    N, M = map(int, input().split())
    edges = [None] * M

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

    ans = BellmanFord(N, M, edges)
    if ans is None:
        print('inf')
    else:
        print(-ans)

def BellmanFord(N, M, edges):
    d = [inf] * N
    d[0] = 0

    for i in range(N-1):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = d[u] + c

    for i in range(N):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = -inf

    if d[N-1] == -inf:
        return None
    else:
        return d[N-1]
    
if __name__ == '__main__':
    solve()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def BellmanFord(E, N, source):
    
    
    
    
    d = [INF for _ in range(N)]
    d[source] = 0
    
    
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and edge[0] == N-1:
                        return -1
    
    return d

N, M = MAP()
abc = [LIST() for _ in range(M)]
G = [[] for _ in range(N)]

for a, b, c in abc:
	G[a-1].append((b-1, -c))

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

Solution (Python):
inf = float('inf')


class Bellmanford:
    def __init__(self, to : list, start : int, goal : int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N
    
    
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
    
    
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle
    
    
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

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

BF = Bellmanford(to, 0, N-1)
BF.update()

if BF.detection_stog():
    ans = "inf"
else:
    ans = -BF.dist[N-1]

print(ans)

Solution (Python):
def bellman_ford(es: list, s: int, inf: int) -> list:
    n = 0
    for e in es: n = max(n, e[0], e[1])
    n += 1
    dis = [inf] * n
    dis[s] = 0
    for t in range(n << 1):
        for e in es:
            if dis[e[0]] != inf and dis[e[1]] > dis[e[0]] + e[2]:
                dis[e[1]] = dis[e[0]] + e[2]
                if t + 1 >= n: dis[e[1]] = -inf
    return dis

if __name__ == '__main__':
    N, M = map(int, input().split())
    es = []
    for i in range(M):
        a, b, c = map(int, input().split())
        es.append((a - 1, b - 1, -c))
    INF = 1 << 60
    dis = bellman_ford(es, 0, INF)
    if dis[N - 1] == -INF: print("inf")
    else: print(-dis[N - 1])

Solution (Python):


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

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

INF = float("inf")
d = [INF] * N
d[0] = 0
"""
最大経路探索的な問題
よくあるベルマンフォード法なら、コストが正の値で、負の閉路が見つかったら失敗、という形で最小経路を求めることになる。
今回は最長経路なので、正の閉路が求まったら失敗にしたい。
なので
・コストを負の値でもつ。表示するときに正に変える
・コストを負にするので閉路を見つけられる
みたいな形にする
"""

def solve(start):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) < d[b]:
                d[b] = d[a] + (-c)
                
                if i == N-1 and b == N-1:
                    return "inf"

    return -1*d[-1]

print(solve(0))

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

def bellman_ford(s,v,e,es):
    
    d = [float("inf")]*v
    d[s] = 0

    for i in range(n):
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i==n-1 and q==n-1:
                    print("inf")
                    exit()
    return d

d=bellman_ford(0,n,m,es)
print(-d[n-1])

Solution (Python):
inf = float('inf')




def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    
    
    
    
    

    
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

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

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)

Solution (Python):
inf = float('inf')

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

dist = [inf] * N
dist[0] = 0
for _ in range(N-1):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w

is_update = [False] * N
for _ in range(N):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w
            is_update[nv] = True
        if is_update[v] is True:
            is_update[nv] = True

if is_update[N-1] is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)