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())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13

G = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = -c
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):
def BellmanFord(edges,num_v,source):
  dist=[float("inf") for i in range(num_v)]
  dist[source]=0
  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != float("inf") and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1 and edge[1] == N - 1:
            return -1
  
  return dist

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

d  = BellmanFord(edges,N,0)
if d==-1:
    print("inf")
    exit()

print(-d[N-1])

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

for i in range(M):
    edges[i][2] *= -1

INF = 10 ** 20
d = [INF] * (N + 1)

def bellman_ford():    
    d[1] = 0
    for _ in range(N):
        for u, v, c in edges:
            if (d[u] != INF) and (d[v] > d[u] + c):
                d[v] = d[u] + c

negative = [False] * (N + 1)

def bellman_ford_neg():
    for _ in range(N):
        for u, v, c in edges:
            if (d[u] != INF) and (d[v] > d[u] + c):
                d[v] = d[u] + c
                negative[v] = True
                
            if negative[u]:
                negative[v] = True

bellman_ford()
bellman_ford_neg()

if negative[-1]:
    print('inf')
else:
    print(-d[-1])

Solution (Python):
n, m = map(int, raw_input().split())
import sys
edges = []
dist = [sys.maxint]*(n+1)
dist[1] = 0
dist
for _ in range(m):
    a, b, c = map(int, raw_input().split())
    edges.append((a, b, -c))

for i in range(n-1):
    for a, b, c in edges:
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
negative = [False] *(n+1)
for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b] or negative[a]:
            negative[b] = True
if negative[n]:
    print "inf"
else:
    print -dist[n]

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

inf = float('inf')

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = -d[V-1]
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
if ans != -d[V-1]:
    print('inf')
else:
    print(ans)

Solution (Python):

def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(n+1):
        for e in p:
            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 [0,'inf']
    return list(map(lambda x:-x, d))

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

Solution (Python):
N,E=map(int,input().split())
G=[]
for i in range(E):
    a,b,c=map(int,input().split())
    G.append([-c,a-1,b-1])
def bellman_ford(G,s):
    INF=10**18
    d=[INF]*N
    d[s]=0
    j=0
    while(True):
        update=False
        for i in range(E):
            cost,fro,to=G[i]
            if d[fro]!=INF and d[to]>d[fro]+cost:
                d[to]=d[fro]+cost
                update=True
                if j==N-1 and to==N-1:
                    return True,0
        if j==N-1:
            return False,d
        j+=1
        if not(update):
            break
    return False,d
bool,d=bellman_ford(G,0)
if bool:
    print("inf")
else:
    print(-d[N-1])

Solution (Python):
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = [False]*N
        for v in V:
            d = dist[v]
            if d != INF:
                for u, c in E[v].items():
                    temp = d + c
                    if dist[u] > temp:
                        updated[u] = True
                        dist[u] = temp
        if sum(updated) == 0: 
            break
    else: 
        if updated[N-1]: return None
        else: return dist
    return dist

N, M = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = -c
V = list(range(N))
dist = bellman_ford(V, E, 0)
if dist is None:
    print('inf')
else:
    print(-dist[N-1])

Solution (Python):
N,M = map(int,input().split())
gra = [[]for i in range(N)]
p = [[0]+[-float("inf")]*(N-1) for i in range(N*2+1)]
p[0][0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    gra[a-1].append([b-1,c])
for i in range(N*2):
    for j in range(N):
        for b,c in gra[j]:
            p[i+1][b] = max(p[i+1][b],p[i][j]+c,p[i][b])
print(["inf",p[N][-1]][p[N][-1] == p[-1][-1]])

Solution (Python):


N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0
d_tmp = 0

for abci in abc: 
    if dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

d_tmp = dist[-1]
for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]    


print(dist[-1]) if d_tmp == dist[-1] else print("inf")

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0
d_tmp = 0

for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

d_tmp = dist[-1]
for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]    


print(dist[-1]) if d_tmp == dist[-1] else print("inf")

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))
graph[1].append((0, 0))

vd = [(N, 0)]

ans = [-INF] * (N + 1)
ans[N] = 0
for _ in range(N + 1):
    nexts = []
    for v, d in vd:
        for u, c in graph[v]:
            if ans[u] < d + c:
                ans[u] = d + c
                nexts.append((u, d + c))
    vd = nexts
if vd:
    print('inf')
else:
    print(ans[0])

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict,deque
branch=defaultdict(dict)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
inf=10**15
dist=[(-inf,set())]*N
dist[0]=(0,{0})
check={0}
while len(check)>0:
    now=check.pop()
    for nex,s in branch[now].items():
        if dist[nex][0]>=inf:
            continue
        if nex not in dist[now][1]:
            dist[nex]=(dist[now][0]+s,dist[now][1]|{nex})
            check|={nex}
        elif dist[now][0]+s>dist[nex][0]:
            dist[nex]=(inf,dist[now][1]|{nex})
            check|={nex}
if dist[N-1][0]>=inf:
    print('inf')
else:
    print(dist[N-1][0])

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


def Bellmanford(n, e, s):
  d = [INF]*n
  d[s] = 0
  for i in range(n):
    for e_from, e_to, e_cost in e:
      if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
        d[e_to] = d[e_from] + e_cost
        if i == n-1 and e_to == n-1:
          return 'inf'
  return -d[n-1]

n,m = (int(x) for x in input().split())
edges = [None] * m

for i in range(m):
    ai, bi, ci = map(int, input().split())
    edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(n, edges, 0)
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(100000)

N, M = [int(ele) for ele in input().split()]
edges = []

d = [-100000000000000000000000000000000000000000000000] * (N+1)
d_tmp = []

for _ in range(M):
    src, dst, w = [int(ele) for ele in input().split()]
    if src == 1:
        d[dst] = w
    edges.append([src, dst, w])

yet = [ele for ele in range(1, N+1)]


def main():
    print(d[-1] if bellman_ford() != -1 else "inf")


def bellman_ford():
    for _ in range(N - 1):
        for src, dst, w in edges:
            if d[dst] < w + d[src]:
                d[dst] = w + d[src]

    d_tmp = d[-1]

    for src, dst, w in edges:
        if d[dst] < w + d[src]:
            d[dst] = w + d[src]

    if d_tmp != d[-1]:
        return -1

    return


if __name__ == "__main__":
    main()

Solution (Python):
n, m = list(map(int, input().split()))
graph = [float("INF") for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(2*n):
  flag = False
  for e in edge:
    a, b, c = e
    a, b, c = a-1, b-1, -c
    if graph[b] > graph[a]+c:
      if b==n-1:
        flag = True
      graph[b] = graph[a]+c
if flag:
  print("inf")
else:
  print(-graph[n-1])

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")


class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1 and edge.to_edge == (node_num - 1):
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)

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

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")


class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if edge.from_edge != INF and dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1 and edge.to_edge == (node_num - 1):
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)

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

Solution (Python):
from operator import itemgetter

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+1):
    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]
        if i==num_v and edge[1]==num_v: return -1

  return dist



N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)

route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-int(route[N-1]))

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


def Bellmanford(node, edges, source):
    d = [INF] * node  
    d[source] = 0

    for i in range(node):
        for start, goal, cost in edges:
            
            
            
            if d[start] != INF and d[start] + cost < d[goal]:
                d[goal] = d[start] + cost
                if i == node-1 and goal == node-1:
                    return 'inf'
    return -d[node-1]


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

for i in range(M):
    ai, bi, ci = abc[i]
    Edges[i] = (ai-1, bi-1, -ci)


ans = Bellmanford(N, Edges, 0)
print(ans)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))

    
    def bellmanford(edge):
        costs = [inf] * N
        costs[0] = 0
        exist_minus_cycle = False
        for i in range(N):
            update = False
            for from_, to, cost in edge:
                cost_to = costs[from_] + cost
                if cost_to < costs[to]:
                    update = True
                    costs[to] = cost_to
                    
            if not update:
                break
            elif i==N-1:
                exist_minus_cycle = True

        
        minus_cycle = set()
        if exist_minus_cycle:
            for i in range(N+1):
                for from_, to, cost in edge:
                    cost_to = costs[from_] + cost
                    if from_ in minus_cycle:
                        minus_cycle.add(to)
                    if cost_to < costs[to]:
                        minus_cycle.add(from_)
                        minus_cycle.add(to)
                        costs[to] = cost_to
        return costs, minus_cycle
    
    costs,minus_cycle = bellmanford(edge)


    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-costs[-1])

if __name__ == '__main__':
    main()

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-1:
            exist_minus_cycle = True

    
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  

def BELLMANFORD(point,d,n):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    d=defaultdict(list)
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append([b,c])
    x,y=(BELLMANFORD(1,d,n))
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  

def BELLMANFORD(point,d,n):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    d=defaultdict(list)
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append([b,c])
    x,y=(BELLMANFORD(1,d,n))
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  

def BELLMANFORD(point,d,n):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    d=defaultdict(list)
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append([b,c])
    x,y=(BELLMANFORD(1,d,n))
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Solution (Python):
import copy

n,w = map(int,input().split()) 
es = [[] for i in range(w)] 
for i in range(w):
    x,y,z = map(int,input().split())
    es[i] = [x,y,-z]
    
w = w

d = [10**20] * (n+1)
d[1] = 0

def find_negative_loop(n,w,es):
    
    
    

    
    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]
                
    return d
find_negative_loop(n,w,es)



D=copy.deepcopy(d)
find_negative_loop(n,w,es)
                

if d[n]==D[n]:
    print(-D[n])
else:
    print("inf")

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

def bellman_ford(V,G,start=0):
    dist = [inf]*V
    dist[start]=0
    negative_cycle = False
    for _ in range(1,V):
        for u in G:
            for v,d in G[u]:
                if dist[v]>dist[u]+d:
                    dist[v] = dist[u]+d
    ans = dist[V-1]
    for u in G:
        for v,d in G[u]:
            if dist[v] > dist[u]+d:
                dist[v] = dist[u]+d
    if dist[V-1]<ans:
        return -1
    else:
        return dist

V,E = map(int,input().split())
G = defaultdict(list)
for i in range(E):
    u,v,d = map(int,input().split())
    G[u-1].append((v-1,-d))
d = bellman_ford(V,G,0)
if d==-1:
    print("inf")
else:
    print(-1*d[V-1])

Solution (Python):
def bellman_ford(x, V, E):
    V[x][0] = 0
    negative = [False for _ in range(len(V))]
    for i in range(len(V) - 2):
        for a, b, c in E:
            if V[b][0] > V[a][0] + c:
                V[b][0] = V[a][0] + c
                V[b][1] = a

    for a, b, c in E:
        if V[b][0] > V[a][0] + c:
            negative[b] = True
        elif negative[a]:
            negative[b] = True

    return V, negative

INF = 10 ** 15
n, m = map(int, input().split())
V = [[INF, 0] for _ in range(n + 1)]
E = []
for i in range(m):
    ai, bi, ci = map(int, input().split())
    E.append([ai, bi, -ci])
V, negative = bellman_ford(1, V, E)
if negative[n]:
    print('inf')
else:
    i = n
    ans = 0
    while(i != 1):
        d, i = V[i]
        ans += d
    print(-V[n][0])

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

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

vi=0
min_dis_list = [10**27 for i in range(N)]
min_dis_list[vi] = 0
prev_list = [-1 for i in range(N)]

for i in range(N-1):
    for e in e_list:
        u,v,d = e
        if min_dis_list[v]>min_dis_list[u]+d:
            min_dis_list[v]=min_dis_list[u]+d
            prev_list[v]=u

neg_loop_flag=[False for i in range(N)]

for i in range(N):
    for e in e_list:
        u,v,d = e
        if min_dis_list[u] + d < min_dis_list[v]:
            neg_loop_flag[v]=True
            min_dis_list[v] = min_dis_list[u] + d
        if neg_loop_flag[u]:
            neg_loop_flag[v]=True
        
if neg_loop_flag[N-1]:
    print("inf")
else:
    print(-min_dis_list[N-1])

Solution (Python):



from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class BellmanFord(object):

    def __init__(self, v_len, edges, start):
        """
        隣接行列を使っていないので、有向グラフにのみ適用可能。
        ベルマンフォード法によって最短経路を求める。
        ダイクストラと違って負の数も扱えるが、O(|V||E|) なのでダイクストラより遅い。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: 辺のリスト
        :param start: 始点 単一視点最短経路問題として解くので必要
        """
        self._dist = [float('inf') for _ in range(v_len)]  
        self._prev = [float('inf') for _ in range(v_len)]  

        self._solve(edges, start)

    def _solve(self, edges, start):
        self._dist[start] = 0

        cnt = 0
        while True:  
            cnt += 1
            updated = False
            for e in edges:
                if self._dist[e.src] + e.cost < self._dist[e.dst]:
                    self._dist[e.dst] = self._dist[e.src] + e.cost
                    self._prev[e.dst] = e.src
                    if cnt >= len(self._dist):
                        self._dist[e.dst] = float('-inf')
                    updated = True
            if not updated:
                break

    def distance(self, goal):
        """
        負の閉路を含む場合は -inf を返す。
        """
        return self._dist[goal]

    def path(self, goal):
        """
        負の閉路を含む場合は計算が終わらない。
        """
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N, M = map(int, input().split())
edges = list()
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, -1 * c))
bf = BellmanFord(N + 1, edges, 1)
print(-1 * bf.distance(N))

Solution (Python):
import time
time0=time.time()

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

EDGELIST=[[] for i in range(N+1)]
EDGEINV=[[] for i in range(N+1)]

for a,b,c in EDGE:
    EDGELIST[a].append([b,c])
    EDGEINV[b].append(a)

SCORE=[float("inf")]*(N+1)


from collections import deque

QUE=deque([N])
while QUE:
    x=QUE.pop()
    SCORE[x]=-float("inf")

    for to in EDGEINV[x]:
        if SCORE[to]==-float("inf"):
            continue
        QUE.append(to)

SCORE[1]=0

QUE=deque([1])

while QUE:

    x=QUE.pop()

    for to,plus in EDGELIST[x]:
        if SCORE[to]<SCORE[x]+plus:
            SCORE[to]=SCORE[x]+plus
            QUE.appendleft(to)

    if time.time()-time0>1.8:
        print("inf")
        break

else:
    print(SCORE[-1])

Solution (Python):
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**13
f=lambda i,j,w: [i-1,j-1,-w]
edge=[f(i,j,w) for i,j,w in edge]
def bf(N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    for i in range(N-1):
        f=0
        for i,j,w in edge:
            if d[j]>d[i]+w:
                d[j]=d[i]+w
                prev[j]=i
                f=1
        if f==0:
            break
    while True:
        f=0
        for i,j,w in edge:
            if d[j]>d[i]+w and (d[j]!=-inf or d[i]!=-inf):
                d[i]=d[j]=-inf
                f=1
        if f==0:
            break
    return d
d=bf(N,0)
if d[N-1]==-inf:
    print('inf')
else:
    print(-d[N-1])