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):
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

    for _ in range(N - 1):
        for a, b, c in E:
            if D[a] == INF:
                continue
            D[b] = min(D[b], D[a] + c)

    ans = D[-1]
    neg = [False] * N

    for _ in range(N):
        for a, b, c in E:
            if D[a] == INF:
                continue

            if D[b] > D[a] + c:
                D[b] = D[a] + c
                neg[b] = True

            if neg[a]:
                neg[b] = True

    print("inf" if ans != D[-1] else -ans)

main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    print("inf" if ans != D[-1] else -ans)

main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = [(a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    print("inf" if ans != D[-1] else -ans)

main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [INF, 0] + [INF] * (N - 1)
    E = tuple(zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    print("inf" if ans != D[-1] else -ans)

main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [INF, 0] + [INF] * (N - 1)
    E = tuple(zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    print("inf" if ans != D[-1] else -ans)

if __name__ == '__main__':
    main()

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

N, M, *ABC = map(int, open(0).read().split())

D = [INF, 0] + [INF] * (N - 1)
E = tuple(zip(*[iter(ABC)] * 3))

for a, b, c in E:
    D[b] = min(D[b], D[a] - c)

ans = D[-1]

for a, b, c in E:
    D[b] = min(D[b], D[a] - c)

print("inf" if ans != D[-1] else -ans)

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n
d[0] = 0
for i in range(n-1):
    for e in E:
        if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
            d[e[1]] = d[e[0]]+e[2]
res =  d[n-1]

for e in E:
    if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
            d[e[1]] = d[e[0]]+e[2]




if  res != d[n-1]:
    print('inf')
else:
    print(res*-1)

Solution (Python):
from collections import deque


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

dic = {}

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []

    dic[a].append([b,c])

lis = [[0] * N for j in range(N)]
lis[0][0] = 1
lmax = [0] * N
lmax[0] = 1

mcost = [-1 * float("inf")] * N
mcost[0] = 0

q = deque([])
q.append(0)
cnt = 0

while len(q) > 0:

    now = q.pop()

    if now not in dic or lmax[now] > N:
        continue

    for npath in dic[now]:

        b = npath[0]
        c = npath[1]

        if mcost[now] + c > mcost[b]:
            mcost[b] = mcost[now] + c
            lis[b] = lis[now].copy()
            lmax[b] = lmax[now]
            lis[b][b] += 1
            lmax[b] = max(lmax[b],lis[b][b])

            if lmax[b] >= 2:
                mcost[b] = float("inf")
            q.append(b)

    if lis[N-1][N-1] != -1 * float("inf") and lmax[N-1] >= 2:
        mcost[N-1] = float("inf")
        break

    elif mcost[N-1] == float("inf"):
        break

print (mcost[N-1])

Solution (Python):
def main():
    import sys
    
    
    N,M = map(int, input().split())
    G = [[] for i in range(N+2)]
    iG = [[] for i in range(N+2)]
    E = []
    for i in range(M):
        a,b,c = map(int,input().split())
        G[a].append([b,-c])
        iG[b].append([a,-c])
        E.append([a,b,c])
        
    from1 = [0]*(N+2)
    toN = [0]*(N+2)
    que = [1]
    while que != []:
        v = que.pop()
        from1[v] = 1
        for L in G[v]:
            b,c = L
            if from1[b] == 0:
                que.append(b)
    que = [N]
    while que != []:
        v = que.pop()
        toN[v] = 1
        for L in iG[v]:
            b,c = L
            if toN[b] == 0:
                que.append(b)
    
    oneN = [0]*(N+2)
    for i in range(N+1):
        oneN[i] = from1[i]*toN[i]
    
    
    itG =[[] for i in range(N+2)]
    for e in E:
        a,b,c = e
        if oneN[a]==oneN[b]==1:
            itG[b].append([a,-c])
            
    import copy
    cost = [float("inf")]*(N+2)
    cost[1] = 0
    for i in range(N+2):
        tmpcost = copy.deepcopy(cost)
        for j in range(1,N+1):
            for e in itG[j]:
                a,c = e
                
                tmpcost[j] = min(tmpcost[j], cost[a]+c)
                
        
        cost = copy.deepcopy(tmpcost)
    flag = 0
    tmpcost = copy.deepcopy(cost)
    for j in range(1,N+1):
        for e in itG[j]:
            a,c = e
            if cost[a]+c < cost[j]:
                
                flag = 1
                break
    
    
    
    
    
    if flag == 1:
        print("inf")
    else:
        print(-cost[N])
    
    
    
main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    dist=[float("inf")]*n
    dist[0]=0
    edges=[0]*m
    for i in range(m):
        a,b,c=map(int,input().split())
        edges[i]=[a-1,b-1,-c]

    
    for k in range(1,2*n): 
        for u,v,cost in edges:
            if dist[v]>dist[u]+cost:
                dist[v]=dist[u]+cost
        if k==n-1:
            ans=dist[n-1]

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

resolve()

Solution (Python):

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


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

edge_list = []
for _ in range(M):
	a, b, c = list(map(int, input().split()))
	a -= 1
	b -= 1
	edge_list.append((a, b, c))
dist = [-(10**20) for _ in range(N)]
dist[0] = 0

for times in range(N):
	for edge in edge_list:
		if dist[edge[0]] > -(10**20):
			if dist[edge[1]] == -(10**20):
				dist[edge[1]] = dist[edge[0]] + edge[2]
			else:
				dist[edge[1]] = max(dist[edge[1]], dist[edge[0]] + edge[2])
score = dist[N - 1]

for times in range(N):
	for edge in edge_list:
		if dist[edge[0]] > -(10**20):
			if dist[edge[1]] == -(10**20):
				dist[edge[1]] = dist[edge[0]] + edge[2]
			else:
				dist[edge[1]] = max(dist[edge[1]], dist[edge[0]] + edge[2])

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

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

def belman(egdes, N, start, end):
    INF = int(1e18)
    cost = [INF] * N
    cost[start] = 0
    fin = False
    count = 0
    while True:
        no_change = True
        for edge in egdes:
            from_, to_, d = edge
            tmp = cost[from_] + d
            if cost[to_] > tmp:
                no_change = False
                cost[to_] = tmp
        count += 1
        if no_change:
            fin = True
            break
        elif count > N+1:
            break
    
    if fin:
        return -cost[end]
    else:
        return "inf"

def bfs(link, N, start):
    q = deque()
    check = [False] * N
    q.append(start)
    check[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for next_ in link[node]:
            if not check[next_]:
                check[next_] = True
                q.append(next_)
                used.add(next_)
    return used
        

def main():
    N, M = map(int, input().split())

    link = [[] for i in range(N)]
    rlink = [[] for i in range(N)]
    edges = []

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        link[a].append(b)
        rlink[b].append(a)
        edges.append((a, b, -c))
    
    use_nodes = bfs(link, N, 0) & bfs(rlink, N, N-1)
    use_edges = [(a, b, c) for a, b, c in edges if a in use_nodes and b in use_nodes]
    print(belman(use_edges, N, 0, N-1))

if __name__ == "__main__":
    main()

Solution (Python):
import collections
import heapq
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a-1][b-1] = -c

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    for _ in range(N-1):
        for a in graph:
            for b in graph[a]:
                dist[b] = min(dist[b], dist[a] + graph[a][b])

    ans = dist[N-1]

    negative = [False for _ in range(N)]
    for _ in range(N):
        for a in graph:
            if dist[a] != float('inf'):
                for b in graph[a]:
                    if dist[b] > dist[a] + graph[a][b]:
                        negative[b] = True
                        dist[b] = dist[a] + graph[a][b]
                    if negative[a] == True:
                        negative[b] = True

    if negative[N-1] == True:
        return "inf"
    else:
        return -ans


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

Solution (Python):
import collections
import heapq
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a-1][b-1] = -c

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    for _ in range(N-1):
        for a in graph:
            for b in graph[a]:
                dist[b] = min(dist[b], dist[a]+graph[a][b])
    ans = dist[N-1]

    negative = [False for _ in range(N)]
    for _ in range(N):
        for a in graph:
            if dist[a] != float('inf'):
                for b in graph[a]:
                    if dist[b] > dist[a] + graph[a][b]:
                        dist[b] = dist[a] + graph[a][b]
                        negative[b] = True
                    if negative[a] == True:
                        negative[b] = True
    if negative[N-1]:
        return 'inf'
    else:
        return -ans

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

Solution (Python):
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
    A[i][2] = -A[i][2]

P = [float("inf")] * (n+1)
P[1] = 0
F = [[0] * 2 for i in range(n+1)]
F[1][0] = 1
F[n][1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans0 = P[:]

for i in range(1):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans1 = P[:]



def d():
    for i in range(n+1):
        if F[i] == [1, 1] and ans1[i] < ans0[i]:
            return "inf"
    return -ans0[n]

print(d())

Solution (Python):
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
    A[i][2] = -A[i][2]

P = [float("inf")] * (n+1)
P[1] = 0
F = [[0] * 2 for i in range(n+1)]
F[1][0] = 1
F[n][1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans0 = P[:]

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans1 = P[:]



def d():
    for i in range(n+1):
        if F[i] == [1, 1] and ans1[i] < ans0[i]:
            return "inf"
    return -ans0[n]

print(d())

Solution (Python):
INF = 10 ** 15


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

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

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

    return ret


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

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

Solution (Python):
n,m = map(int,input().split())
edge = []
for _ in range(m):
  a,b,c = map(int,input().split())
  edge.append((a,b,-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
f = 0
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        f = 1
ans = dis[n]
if f:
  for _ in range(n):
    for a,b,c in edge:
      if dis[b] > dis[a] + c:
        dis[b] = dis[a] + c
        if b == n:
          print("inf")
          exit(0)
print(-ans)

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

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

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N-1]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

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


main()

Solution (Python):
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

for n in range(N):
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            if b == N and n == N - 1:
                print("inf")
                sys.exit()

print(-distance[N - 1])

Solution (Python):

import sys

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

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



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

if __name__ == '__main__':
    main()

Solution (Python):

import sys

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

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



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

if __name__ == '__main__':
    main()

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

def BellmanFord(n,m,graph):
    costs=[float("inf")]*n
    costs[0]=0
    for _ in range(n-1):
        for i in range(m):
            if costs[graph[i][1]]>costs[graph[i][0]]+graph[i][2]:
                costs[graph[i][1]]=costs[graph[i][0]]+graph[i][2]
    newcosts=[]
    for i in costs:
        newcosts.append(i)
    for _ in range(n):
        for i in range(m):
            if newcosts[graph[i][1]]>newcosts[graph[i][0]]+graph[i][2]:
                newcosts[graph[i][1]]=newcosts[graph[i][0]]+graph[i][2]
    if newcosts[n-1]!=costs[n-1]:
        return "inf"
    else:
        return -costs[n-1]

print(BellmanFord(n,m,graph))

Solution (Python):
inf = float("inf")
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a - 1, b - 1, c))
d = [-inf] * N
d[0] = 0
for i in range(N):
    for a, b, c in edges:
        if d[b] < d[a] + c:
            d[b] = d[a] + c
for i in range(N):
    for a, b, c in edges:
        if d[b] < d[a] + c:
            d[b] = inf
print(d[N - 1])

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

def bellman_ford(v, s, e):
    INF = 10**18
    
    d = [INF] * v
    
    d[s] = 0
    
    for i in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
                if i==v-1 and b==v-1:
                    return -1
        
        if not f:
            break

    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a-1,b-1,-c))

ans=bellman_ford(n,0,e)
if ans==-1:
    print("inf")
else:
    print(-ans[-1])

Solution (Python):
n,m=map(int,input().split())
abc=[]
for i in range(m):
    abc.append([int(j) for j in input().split()])
b=[float("INF")]*(n+1)
b[1]=0
for i in range(1,n+1):
    for s,t,u in abc:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:
                print("inf")
                exit()
print(-b[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
def find_negative_loop(s,n,w,es):
  
  
  
  
  
  
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         
n, m = map(int, input().split())
es = []
for i in range(m):
  a, b, c = map(int, input().split())
  es.append([a-1, b-1, c*(-1)])
  
temp, d = find_negative_loop(0, n, m ,es)
if temp == d:
  print(d*(-1))
else:
  print('inf')

Solution (Python):
n,m=map(int,input().split());a,b=[list(map(int,input().split()))for i in range(m)],[float("INF")]*(n+1);b[1]=0
for i in range(1,n+1):
    for s,t,u in a:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:print("inf");exit()
print(-b[-1])

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    dist = [-inf for _ in range(n)]
    dist[start] = 0
    for cnt in range(n+1):
        for edge in edges:
            e_from, e_to, e_cost = edge
            if dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
        if cnt == n - 1:
            d = dist[:]
    if d[-1] < dist[-1]:
        print('inf')
        quit()
    else:
        return d[-1]

n,m = LI()
edges = []
for _ in range(m):
    a,b,c = LI()
    edges.append([a-1,b-1,c])

ans = Bellman_Ford(edges,0)
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    dist = [-inf for _ in range(n)]
    dist[start] = 0
    for cnt in range(n+1):
        for edge in edges:
            e_from, e_to, e_cost = edge
            if dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
        if cnt == n - 1:
            d = dist[:]
    if d[-1] < dist[-1]:
        print('inf')
        quit()
    else:
        return d[-1]

n,m = LI()
edges = []
for _ in range(m):
    a,b,c = LI()
    edges.append([a-1,b-1,c])

ans = Bellman_Ford(edges,0)
print(ans)

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

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

visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]


def bellman_ford(n, edge):
    INF = float('inf')
    d = [INF] * n
    d[0] = 0
    for i in range(n):
        update = False
        for v_from, v_to, cost in edge:
            if v_from not in target_nodes or v_to not in target_nodes:
                continue
            if d[v_from] != INF and d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost 
                update = True
    return d, update

d, update = bellman_ford(n, edge)
if update:
    print("inf")
else:
    print(-d[n-1])

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford() -> int or None:
    dist = [-float("inf")] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if dist[v] + w > dist[u]:
                dist[u] = dist[v] + w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    global N, M, E
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford()
    flg = ans is not None
    print(ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford() -> int or None:
    dist = [float("inf")] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    global N, M, E
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford()
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if v != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if v != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if v != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()