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):
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: -float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)
        self.x = 0
        self.y = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        c = 0
        while self.Q:
            c += 1
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
            if c == 2100:
                self.x = self.dist[N]
            if c >= 200000:
                self.y = self.dist[N]
                break
    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

g_a = Graph()
for i in range(M):
    a, b, w = list(map(int, input().split()))
    g_a.add_edge(a, b, w)

s = 1
d_a = Dijkstra(g_a, s)

if d_a.x == d_a.y:
    print(d_a.dist[N])
else:
    print("inf")

Solution (Python):
n, m = map(int, input().split())
abc = []

INF = 10 ** 20

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

dist = [INF for _ in range(n)]
dist[0] = 0

for i in range(n - 1):
    for a, b, c in abc:
        if dist[a] == INF:
            continue
        elif dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

ans = dist[n - 1]

check = [-1 for _ in range(n)]

for i in range(n - 1):
    for a, b, c in abc:
        if dist[a] == INF:
            continue
        elif dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            check[b] = 0

if check[n-1] == 0:
    print('inf')
else:
    print(-ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007








def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n-1):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
        if not update:
            break
    negative = [False for i in range(n)]
    for j, k, l in adj:
        if dist[k] > dist[j] + l:
            dist[k] = dist[j] + l
            negative[k] = True
    return dist,negative[n-1]
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,-c])
d,ne = bellman_ford(0)
if ne:
    print("inf")
else:
    print(-d[-1])

Solution (Python):
n,m=map(int,input().split())
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    e.append([a-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
v=0
while k<n*2:
    k+=1
    if k==n:v=d[-1]
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
if not v or v==d[-1]:
    print(-d[-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-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
v=0
while k<n*2:
    k+=1
    if k==n:v=d[-1]
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
if not v or v==d[-1]:
    print(-d[-1])
else:
    print('inf')

Solution (Python):
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)) 

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print(maxdis[n-1])

Solution (Python):
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)) 

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(2*n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print(maxdis[n-1])

Solution (Python):
n, m = map(int, input().split())
INF = pow(10, 15)

alist, blist, clist = [], [], []
for _ in range(m):
  a, b, c = map(int, input().split())
  alist.append(a-1)
  blist.append(b-1)
  clist.append(-c)
dist = [INF for _ in range(n)]
dist[0] = 0
for _ in range(n-1):
  for a, b, c in zip(alist, blist, clist):
    if dist[a] == INF:  
      continue
    if dist[b] > dist[a] + c:  
      dist[b] = dist[a] + c

ans = dist[n-1]

negative = [False for _ in range(n)]

for _ in range(n):
  for a, b, c in zip(alist, blist, clist):
    if dist[a] == INF:
      continue
    if dist[b] > dist[a] + c:
      dist[b] = dist[a] + c
      negative[b] = True
    if negative[a]:
      negative[b] = True

if negative[n-1]:
  print("inf")
else:
  print(-ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
neg=[False]*(N+1)
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        neg[b]=True
    if neg[a]==True:
      neg[b]=True
if neg[N]:
  print("inf")
  exit(0)
print(allcost[N])

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


def shortest_path(s):
    
    
    d = [float("inf")] * n
    
    d[s] = 0
    for j in range(n):
        updata = False
        for i in range(w):
            e = es[i]
            
            if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                updata = True
        if not updata:
            break
    tmp = d[-1]
    for j in range(n):
        updata = False
        for i in range(w):
            e = es[i]
            
            if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                updata = True
        if not updata:
            break
    if tmp == d[-1]:
        return d[-1]
    return float("inf")

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

es = []

for i in range(w):
    x,y,z = map(int,input().split())
    es.append([x-1,y-1,-z])
dj = shortest_path(0)
if dj == float("inf"):
    print('inf')
else:
    print(-dj)

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
edges = defaultdict(list)
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edges[a].append((b, c))
INF = 10 ** 18

def bellman_ford():
    scores = [-INF] * N
    scores[0] = 0
    for i in range(N):
        for v in range(N):
            if scores[v] == -INF:
                continue
            for to, sc in edges[v]:
                if scores[v] + sc > scores[to]:
                    scores[to] = scores[v] + sc
                    if i == N - 1 and to == N - 1:
                        return 'inf'
    return scores[N - 1]

ans = bellman_ford()
print(ans)

Solution (Python):
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])


inf=float("inf")
dist=[inf for i in range(n)]
dist[0]=0
flag = False
for i in range(2*n):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            if i >= n-1 and edge[1] == n-1:
                flag = True
                break
if flag:
    print("inf")
else:
    print(-dist[n-1])

Solution (Python):

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

dists = [float('inf')] * N 
def bellman_ford(edges:list, start:int)->bool:
    """O(|V|*|E|)
    param v:
    param edges:
    return (exist negative loop)
    """
    global dists
    dists[start] = 0
    V = len(dists)
    for i in range(V):
        for (s,t,w) in edges:
            if isinf(dists[s]): continue
            if dists[t] > dists[s]+w:
                dists[t] = dists[s]+w
                if i==V-1 and t==V-1:
                    return True
        
    return False

negativeLoop = bellman_ford(e, 0)
if negativeLoop:
    print('inf')
else:
    print(-dists[-1])

Solution (Python):
n,m=map(int,input().split())
es=[list(map(int,input().split())) for _ in range(m)]
inf=float("inf")
d=[-inf]*(n+1)
d[1]=0

def bellman_ford():
  for i in range(n):
    isUpdated=False
    for e_from,e_to,cost in es:
      if d[e_to]<d[e_from]+cost:
        d[e_to]=d[e_from]+cost
        isUpdated=True
        if i==n-1 and e_to==n:return inf
    if not isUpdated:
      break
  return d[n]

print(bellman_ford())

Solution (Python):
def BellmanFord(edges,num_vertex,start):
    inf=float("inf")
    dist=[inf for i in range(num_vertex)]
    dist[start]=0
    for i in range(num_vertex):
        for edge in edges:
            if dist[edge[0]]!=inf and dist[edge[1]]>dist[edge[0]]+edge[2]:
                dist[edge[1]]=dist[edge[0]]+edge[2]
                if i==num_vertex-1 and edge[1]==num_vertex-1:
                    return -1
    return dist

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=BellmanFord(edges,n,0)
if dist==-1:
    print("inf")
else:
    print(-dist[-1])

Solution (Python):
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N + 23):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N + 22 and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


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


if __name__ == '__main__':
    main()

Solution (Python):
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N + 1):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


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


if __name__ == '__main__':
    main()

Solution (Python):
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N - 1 and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


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


if __name__ == '__main__':
    main()

Solution (Python):

n,m=map(int,input().split())
edge=[]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append((a-1,b-1,-c))
inf=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while count<n+1:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break
else:
    print(-d[n-1])

Solution (Python):
def BellmanFord(edges, num_v, source):
    
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                
                
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = map(int, input().split())
edges = []
for _ in range(num_e):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print(-dist[-1])

Solution (Python):
def BellmanFord(edges, num_v, source):
    
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = map(int, input().split())
edges = []
for _ in range(num_e):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print(-dist[-1])

Solution (Python):

def shortest_path(edges, num_v, start):
    inf = float("inf")
    dist = [inf for _ in range(num_v)]
    dist[start] = 0
    
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]] != 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] == num_v - 1:
                    print("inf")
                    exit()
    return dist

n, m = [int(i) for i in input().split()]
edges = []
for _ in range(m):
    a, b, c = [int(i) for i in input().split()]
    edges.append([a-1, b-1, -c])
out = shortest_path(edges,n,0)
print(-out[-1])

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

inf = float('inf')
d = [inf]*(N+1)
d[1] = 0
for i in range(N+1):
    for v, nv, cost in G:
        if d[v] != inf and d[nv] > d[v]+cost:
            d[nv] = d[v]+cost
            if i == N-1:
                tmp = d[N]
            if i == N and d[N] != tmp:
                print('inf')
                exit()
print(-d[N])

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

inf = float('inf')
d = [inf]*(N+1)
d[1] = 0
for i in range(N+1):
    for v, nv, cost in G:
        if d[v] != inf and d[nv] > d[v]+cost:
            d[nv] = d[v]+cost
            if i == N-1:
                tmp = d[N]
            if i == N and d[N] != tmp:
                print('inf')
                exit()
print(-d[N])

Solution (Python):
import sys


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


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N-1):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d

for a, b, c in edge:
    c = -c
    new_d = d[a]+c
    if d[b] > new_d:
        d[b] = new_d
        if b == N:
            print('inf')
            exit()
print(-d[-1])

Solution (Python):


"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

def bellman_ford(N, edges, start):
    
    
    verts = [float('inf')] * N
    verts[start] = 0
    
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    
    for src, dest, cost in edges:
        if verts[src] + cost < verts[dest]:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                
                return []
    
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    
    print(-verts[N-1])

Solution (Python):
import sys


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


N, M = (list)(map(int, input().split()))
edge = []

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

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

Solution (Python):


"""
参考：https://img.atcoder.jp/abc061/editorial.pdf
・ベルマンフォード
・負の閉路があっても、そこに頂点Nが含まれなければ今回はOK
　って点に気付けなかったー。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

def bellman_ford(N: int, edges: list, start: int) -> list:
    
    
    verts = [float('inf')] * N
    verts[start] = 0
    
    for i in range(N-1):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
    
    for src, dest, cost in edges:
        if verts[dest] > verts[src] + cost:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                
                return []
    
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    
    print(-verts[N-1])

Solution (Python):


"""
参考：https://img.atcoder.jp/abc061/editorial.pdf
・ベルマンフォード
・負の閉路があっても、そこに頂点Nが含まれなければ今回はOK
　って点に気付けなかったー。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

def bellman_ford(N: int, edges: list, start: int) -> list:
    
    
    verts = [float('inf')] * N
    verts[start] = 0
    
    for i in range(N-1):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
    
    for i in range(N):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
                if dest == N-1:
                    
                    return []
    
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    
    print(-verts[N-1])

Solution (Python):


"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

def bellman_ford(N: int, edges: list, start: int) -> list:
    
    
    verts = [float('inf')] * N
    verts[start] = 0
    
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    
    for src, dest, cost in edges:
        if verts[src] + cost < verts[dest]:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                
                return []
    
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    
    print(-verts[N-1])

Solution (Python):


"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

def bellman_ford(N: int, edges: list, start: int) -> list:
    
    
    verts = [float('inf')] * N
    verts[start] = 0
    
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    
    for i in range(N):
        for src, dest, cost in edges:
            if verts[src] + cost < verts[dest]:
                verts[dest] = verts[src] + cost
                if dest == N-1:
                    
                    return []
    
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    
    print(-verts[N-1])

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

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

for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()

print(-dist[-1])

Solution (Python):
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        """
        graph : [[a1,b1,c1],[a2,b2,c2],‥]みたいな3次元配列のリスト,a1からb1までのコストはc1
        num_v :頂点の数
        start_point :スタート地点(a1)
        """
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
 
 
    def execute(self):
        dist = [-1*float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        negative = [False for _ in range(self.num_v)]

        for i in range(self.num_v - 1):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost

        for i in range(self.num_v):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost
                    negative[end] = True
                if negative[start]:
                    negative[end] = True
        return dist, negative

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

bellman = BellmanFord(E, N, 0)
result, negative = bellman.execute()
 
if negative[-1]:
    print("inf")
else:
    print(result[-1])

Solution (Python):
N, M = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*k)

INF = float('inf')

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

negative = [False] * N

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

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

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

Solution (Python):
N, M = [int(_) for _ in input().split()]
T = [[int(_) for _ in input().split()] for i in range(M)]

E = []
for a, b, c in T:
    E.append((a - 1, b - 1, c))

min_V = -1000000000 * 2000
scores = [min_V] * N
scores[0] = 0

for i in range(N):
    for a, b, c in E:
        if scores[b] >= scores[a] + c:
            continue
        scores[b] = scores[a] + c

ans = scores[N - 1]

for a, b, c in E:
    if scores[b] >= scores[a] + c:
        continue
    scores[b] = scores[a] + c

if ans != scores[N-1]:
    print("inf")
else:
    print(scores[N - 1])

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())
	A[i] -= 1
	B[i] -= 1
inf = 123456789123456789123456789
dist = [ -inf ] * N
dist[0] = 0
bounded = True
for i in range(max(2 * N - 3, 4)):
	for j in range(M):
		if dist[B[j]] < dist[A[j]] + C[j]:
			dist[B[j]] = dist[A[j]] + C[j]
			if B[j] == N - 1 and i >= N:
				bounded = False
if not bounded:
	print("inf")
else:
	print(dist[N - 1])

Solution (Python):
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0
        negative = [False for _ in range(self.num_v)]
        for i in range(self.num_v - 1):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    negative[dest] = True
                if negative[src]:
                    negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a-1, b-1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])

Solution (Python):
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0
        negative = [False for _ in range(self.num_v)]
        for i in range(self.num_v - 1):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    negative[dest] = True
                if negative[src]:
                    negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a-1, b-1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])