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())
a = [0] * M
b = [0] * M
c = [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    c[i] = -c[i]
    
INF = 10 ** 13
dist = [INF] * N

dist[0] = 0

for loop in range(N-1):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]

ans = dist[N-1]

nega = [0] * N

for loop in range(N):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]
            nega[b[i]-1] = 1
        if nega[a[i]-1] == 1:
            nega[b[i]-1] = 1

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

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
E=[]
for i in range(m):
    a,b,c=map(int,input().split())
    E.append((a-1,b-1,c))
INF=-10**20
score=[INF]*n
score[0]=0
for i in range(n-1):
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]<score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
negative=[False]*n
for i in range(n):
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]<score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
                negative[e[1]]=True
if negative[n-1]:
    print('inf')
else:
    print(score[n-1])

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

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

INF = float("inf")
d = [INF] * N 
d[0] = 0

for i in range(N):
    for f, t, c in es:
        f, t = f-1, t-1
        c = c * -1 
        if d[f] != INF and d[t] > d[f] + c: 
            d[t] = d[f] + c
            if i == N-1 and t == N-1: 
                print("inf")
                exit()

print(-d[-1])

Solution (Python):
from sys import stdin

INF = float('inf')


def bellman_ford(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]


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    Edges = [None] * M

    for i in range(M):
        ai, bi, ci = [int(x) for x in stdin.readline().rstrip().split()]
        Edges[i] = (ai-1, bi-1, -ci)

    ans = bellman_ford(N, Edges, 0)

    print(ans)


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

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



def BF(E,s,n):
  inf=float("inf")
  d=[inf for _ in range(n)]
  d[s]=0
  for i in range(n+1):
    for e in E:
      if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
        d[e[1]-1] = d[e[0]-1] + e[2]
    if i==n-1:t=d[-1]
    if i==n and t!=d[-1]:
      return 'loop'
  return d

def main():
  N,M = II()
  E = []
  for _ in range(M):
    a,b,c = II()
    E.append([a,b,-c])

  d = BF(E,0,N)

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

if __name__ == '__main__':
  main()

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



def BF(E,s,n):
  inf=float("inf")
  d=[inf for _ in range(n)]
  d[s]=0
  for i in range(n+1):
    for e in E:
      if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
        d[e[1]-1] = d[e[0]-1] + e[2]
    if i==n-1:t=d[-1]
    if i==n and t!=d[-1]:
      return 'loop'
  return d

N,M = II()
E = []
for i in range(M):
  a,b,c = II()
  E.append([a,b,-c])

d = BF(E,0,N)

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

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

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    print(a)
else:
    print("inf")

Solution (Python):
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def remove_Edge(N,Ef,Eb,start,goal):
    v = connect_dfs(N,Ef,start) & connect_dfs(N,Eb,goal)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            Ef[j].pop(i)

def Bellman_Ford(N,E,start,INFTY=10**18):
    def update(dist,N,E,start):
        done = [False]*N
        done[start] = True
        q = [start]
        d = dist[:]
        while q:
            i = q.pop()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    q.append(j)
                    done[j] = True
        return d
    
    d = [INFTY]*N
    d[start] = 0
    for _ in range(N-1):
        d = update(d,N,E,start)
    if d!=update(d,N,E,start):
        return None
    else:
        return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]
    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    
    remove_Edge(N,E,Eb,0,N-1)
    d = Bellman_Ford(N,E,0)
    if d == None:
        print("inf")
    else:
        print(-d[-1])
    
main()

Solution (Python):
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def update(dist,N,E,start):
    done = [False]*N
    done[start] = True
    q = [start]
    d = dist[:]
    while q:
        i = q.pop()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                q.append(j)
                done[j] = True
    return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    v = connect_dfs(N,E,0) & connect_dfs(N,Eb,N-1)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    for _ in range(N-1):
        d = update(d,N,E,0)
    if d!=update(d,N,E,0):
        print("inf")
    else:
        print(-d[-1])

main()

Solution (Python):
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = -c

    
    V1 = [False]*N
    V1[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        for j in E[i]:
            if V1[j]:continue
            qa(j)
            V1[j]=True
    V2 = [False]*N
    V2[-1] = True
    qa(N-1)
    while q:
        i = qp()
        for j in Eb[i]:
            if V2[j] or not V1[j]:continue
            qa(j)
            V2[j]=True
    for i in range(N):
        if V1[i] and V2[i]:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    def update():
        done = [False]*N
        done[0] = True
        q = [0]
        qp = q.pop
        qa = q.append
        while q:
            i = qp()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    qa(j)
                    done[j] = True

    for _ in range(N-1):update()
    dc = d[:]
    update()
    if dc!=d:
        print("inf")
    else:
        print(-d[-1])
main()

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

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c
    Eb[b-1][a-1] = -c


V1 = [False]*N
V1[0] = True
q = [0]
qp = q.pop
qa = q.append
while q:
    i = qp()
    for j in E[i]:
        if V1[j]:continue
        qa(j)
        V1[j]=True
V2 = [False]*N
V2[-1] = True
qa(N-1)
while q:
    i = qp()
    for j in Eb[i]:
        if V2[j] or not V1[j]:continue
        qa(j)
        V2[j]=True
for i in range(N):
    if V1[i] and V2[i]:continue
    for j in Eb[i]:
        E[j].pop(i)

INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True
                
for _ in range(N-1):update()
dc = d[:]
update()
if dc!=d:
    print("inf")
else:
    print(-d[-1])

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

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c
    Eb[b-1][a-1] = -c


V1 = [False]*N
V1[0] = True
q = [0]
qp = q.pop
qa = q.append
while q:
    i = qp()
    for j in E[i]:
        if V1[j]:continue
        qa(j)
        V1[j]=True
V2 = [False]*N
V2[-1] = True
qa(N-1)
while q:
    i = qp()
    for j in Eb[i]:
        if V2[j] or not V1[j]:continue
        qa(j)
        V2[j]=True
for i in range(N):
    if V1[i] and V2[i]:continue
    for j in Eb[i]:
        E[j].pop(i)

INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True
                
for _ in range(N-1):update()
dc = d[:]
update()
if dc!=d:
    print("inf")
else:
    print(-d[-1])

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

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c


INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True

for _ in range(N-1):update()
dc = d[:]
for _ in range(N):update()
if dc[-1]!=d[-1]:
    print("inf")
else:
    print(-d[-1])

Solution (Python):
def main():
    N, M = map(int, input().split())
    g = []
    INF = 10 ** 9 * 1000
    d = [INF] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != INF and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print(-d[-1])


main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    g = []
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != float('INF') and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print(-d[-1])


main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        c = -c
        g[a].append((b, c))
    for i in range(2 * N):
        for x, r in enumerate(g):
            for y, c in r:
                if d[x] != float('INF') and d[y] > d[x] + c:
                    d[y] = d[x] + c
                    if y == N and i > N:
                        print("inf")
                        exit()

    print(-d[-1])


main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    INF = -1 * 10 ** 9 * 1000
    d = [INF] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g[a].append((b, c))
    for i in range(2 * N):
        for x, r in enumerate(g):
            for y, c in r:
                if d[x] != INF and d[x] + c > d[y]:
                    d[y] = d[x] + c
                    if y == N and i > N:
                        print("inf")
                        exit()

    print(d[-1])


main()

Solution (Python):

N,M = list(map(int,input().split(" ")))
INF = -(10 ** 20)
graph = [ INF for _ in range(N + 1)]
edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split(" ")))
    edges.append((a,b,c))

graph[1] = 0
for i in range(2 * N): 
    for edge in edges:
        fr,to,point = edge
        if graph[fr] + point >  graph[to] and  graph[fr] != INF:
            graph[to] = graph[fr] + point
            if to == N and i > N:
                print("inf")
                exit()

print(graph[-1])

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

def main():
    N, M = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = 10**14
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    if ans == V[N-1]:
        print(-ans)
    else:
        print("inf")
        
if __name__ == '__main__':
    main()

Solution (Python):

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

edges = []

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

dist = [float('inf')] * (N + 1)
dist[1] = 0

for _ in range(N - 1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] - c)

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

if ans == dist[N]:
    print(-ans)
else:
    print('inf')

Solution (Python):
from collections import defaultdict

def main():
    node_num, edge_num = map(int, input().split())
    graph_data = [list(map(int, input().split())) for i in range(edge_num)]
    inf = -10 ** 15
    length_data = [inf for i in range(node_num + 1)]
    length_data[1] = 0

    ans_data = length_data[node_num]
    for i in range(node_num):
        for a, b, c in graph_data:
            b_lengh = length_data[a] + c
            length_data[b] = max(b_lengh, length_data[b])
        
        if i == node_num - 1 and length_data[node_num] > ans_data:
            ans_data = 'inf'
        else:
            ans_data = length_data[node_num]

    print(ans_data)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    [N, M] = [int(i) for i in input().split()]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen

    dist2 = dist.copy()

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist2[a-1] + c
            if newLen > dist2[b-1]:
                dist2[b-1] = newLen

    if dist[N-1] != dist2[N-1]:
        print('inf')
    else:
        print(dist[N-1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    [N, M] = [int(i) for i in input().split()]
    edge = [[10**100] * N for _ in range(N)]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    flag = False

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen
        if i == N-1 and dist[N-1] > predist:
            flag = True
        predist = dist[N-1]

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


if __name__ == '__main__':
    main()

Solution (Python):
N,M = [int(s) for s in input().split()]
dist = [N*-10**9]*N
E = []
flag = 0
change = 0
N_flag = 0
for i in range(M):
    a,b,c = [int(s) for s in input().split()]
    E.append((a,b,c))
dist[0] = 0
for i in range(N):
    for (a,b,c) in E:
        if a == N or b == N:
            N_flag = 1
        newLen = dist[a-1] + c
        if newLen > dist[b-1]:
            change = 1
            dist[b-1] = newLen
            if i == N-1 and change == 1 and N_flag == 1:
                flag = 1
        change = 0
        N_flag = 0
if flag == 1:
    print('inf')
else:
    print(dist[N-1])

Solution (Python):
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]
                
                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):
        
        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 and e[1] == numNodes-1:
                        return True, d
        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_bool(0, N)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Solution (Python):
N, M = map(int, input().split())
E = []
for _ in range(M):
    a,b,c = map(int, input().split())
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            dist[b] = newlen
    if i == N-1 and dist[N] > predist:
        flag =True
    predist = dist[N]

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

Solution (Python):



def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    
    for i in range(n<<1):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
        if i <= n: a0 = dist[-1]
    if a0 != dist[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))


dist, TF = Bellman_Ford(g, 0)

if TF: print(-dist[-1])
else: print("inf")

Solution (Python):
N, M = map(int, input().split())
E = []
for _ in range(M):
    a,b,c = map(int, input().split())
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            if i == N-1:
                flag = True
            dist[b] = newlen
            predist = dist[N]

dist2 = dist.copy()
for i in range(N):
    for (a,b,c) in E:
        newlen = dist2[a] + c
        if newlen > dist2[b]:
            dist2[b] = newlen
if dist2[N] > dist[N]:
    print("inf")
else:
    print(dist[N])

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import sys

sys.setrecursionlimit(100000)

def main():
    N, M = readi(2)
    edges = readi(M, 3)
    dist = arr(N + 1, fill_value=float("-inf"))
    dist[1] = 0
    for i in range(N - 1):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                dist[b] = new_d
    
    ans = dist[N]

    for i in range(N - 1):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                dist[b] = new_d

    if ans != dist[N]:
        print('inf')
    else:
        print(dist[N])


if __name__ == "__main__":
    main()

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import sys

sys.setrecursionlimit(100000)

def main():
    N, M = readi(2)
    edges = readi(M, 3)
    pred = defaultdict(list)
    for a, b, _ in edges:
        pred[b].append(a)
    
    s = set()
    s2 = set()

    def rec(n):
        if n not in s2:
            s2.add(n)
            for m in pred[n]:
                s.add(m)
                rec(m)

    rec(N)
    
    dist = arr(N + 1, fill_value=float("-inf"))
    dist[1] = 0
    for i in range(N):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                if i == N - 1 and b in s:
                    print("inf")
                    return
                dist[b] = new_d
    print(dist[N])


if __name__ == "__main__":
    main()

Solution (Python):



def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    negative = [False]*n
    for i in range((2*n)):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if negative[v]: negative[to] = True
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
                if i >= n:
                    negative[to] = True
        if not updated: break
    if negative[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))


dist, TF = Bellman_Ford(g, 0)

if TF: print(-dist[-1])
else: print("inf")

Solution (Python):
class BellmanFord():
	def __init__(self, adj, start):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		return

	
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for x in range(self.size):
			for y, w in self.adj[x]:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		if res != self.dist[goal]:
			return True
		else:
			return False

	def GetDistance(self, goal):
		return self.dist[goal]

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

bf = BellmanFord(adj, 0)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print("inf")
else:
	print(-bf.GetDistance(n-1))

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		return

	
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for x in range(self.size):
			for y, w in self.adj[x]:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		if res != self.dist[goal]:
			return True
		else:
			return False

	def GetDistance(self, goal):
		return self.dist[goal]

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

bf = BellmanFord(adj, 0)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print("inf")
else:
	print(-bf.GetDistance(n-1))

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

INF = - 10 ** 20
d = [INF for _ in range(N)]
d[0] = 0

for i in range(2 * N):
  f = True
  rel = d[-1]
  for j in range(M):
    a, b, c = abc[j]
    a -= 1
    b -= 1
    if d[b] < d[a] + c:
      d[b] = d[a] + c
      f = False
  if f:
    break
else:
  if rel != d[-1]:
    print("inf")
    exit()

print(d[-1])

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