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



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    #new_cost = dist_list[j] + edge[1]
                    if dist_list[j] + edge[1] < dist_list[edge[0]]:
                        dist_list[edge[0]] = dist_list[j] + edge[1]
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 2 << 40
G, dist = [None for i in range(M)], [INF for j in range(N)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(2*N):
        for j in range(M):
            e = G[j]
            if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i >= N - 1 and (e.t == N - 1 or e.f == N - 1):
                    return True

    return False


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

    c = bellman_ford(0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
data = []
for i in range(0,m):
    a,b,c = map(int,input().split())
    data.append((a,b,-c))

g = [float("inf") for _ in range(0,n+1)]
g[1] = 0
negative = ["false" for _ in range(0,n+1)]

for i in range(0,n):
    for j in range(0,m):
        a,b,c = data[j]
        if g[a] != float("inf") and g[b] > g[a] + c:
            g[b] = g[a] + c
            if i == n-1:
                negative[b] = "true"
if negative[n] == "false":
    print(-g[n])
else:
    print("inf")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]
C = [-float("inf")] * (N+1)
C[1] = 0
for i in range(N-1):
    for e in E:
        a, b, c = e
        C[b] = max(C[b], C[a]+c)
ans = C[N]
for i in range(N):
    for e in E:
        a, b, c = e
        C[b] = max(C[b], C[a]+c)
if C[N] == ans:
    print(ans)
else:
    print("inf")

Submission status: Accepted

Solution code:
def bellmanford(xyw, n, start):
    inf = float("inf")
    dist = [inf]*n
    dist[start] = 0

    for _ in range(n-1):
        for x,y,w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
    result = dist[n-1]
    negative = [0]*n
    for _ in range(n):
        for x, y, w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                negative[y] = True
            if negative[x]:
                negative[y] = True
    return inf if negative[n-1] else -result


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

print(bellmanford(ABC, N, 0))

Submission status: Accepted

Solution code:
N,M =map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(M)]
abc = [(a-1,b-1,-c) for a,b,c in abc]

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

for _ in range(N-1):
    for a,b,c in abc:
        if dist[a] == float('inf'):
            continue
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

ans = dist[N-1]
negative = [False]*N

for _ in range(N):
    for a,b,c in abc:
        if dist[a] == float('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)

Submission status: Accepted

Solution code:
import sys
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=10**30
dist=[inf]*N
dist[0]=0
for i in range(N):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
ans = dist[N-1]
visit=[False]*N
for i in range(N):
    for x,y,z in edge:
        if visit[x]:
            visit[y]=True
        if dist[y]<= dist[x]+z:
            continue
        visit[y]=True
        dist[y]=dist[x]+z
        
if visit[N-1]:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

Solution code:
import sys
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=10**30
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==N and y==N-1:
            print('inf')
            sys.exit()
print(-dist[N-1])

Submission status: Accepted

Solution code:
import sys
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=10**30
dist=[inf]*N
dist[0]=0
for i in range(N):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
ans = dist[N-1]
visit=[False]*N
for i in range(N):
    for x,y,z in edge:
        if visit[x]:
            visit[y]=True
        if dist[y]<= dist[x]+z:
            continue
        visit[y]=True
        dist[y]=dist[x]+z
        
if visit[N-1]:
    print('inf')
else:
    print(-dist[N-1])

Submission status: Accepted

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

a, b, c = [([0]*m) for _ in range(3)] 
for i in range(m):
    d,e,f = map(int, input().split())
    a[i] = d-1
    b[i] = e-1
    c[i] = -f

d = [INF]*n
d[0] = 0

for _ in range(n-1):
    for x,y,z in zip(a,b,c):
        if d[x] == INF:
            continue
        d[y] = min(d[y], d[x]+z)

ans = -d[-1]
negative = [False]*n

for _ in range(n):
    for x,y,z in zip(a,b,c):
        if d[x] == INF:
            continue
        if d[y] > d[x]+z:
            d[y] = d[x]+z
            negative[y] = True
        negative[y] |= negative[x]

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

Submission status: Accepted

Solution code:
def BellmanFord(x,n,s):
	inf = float("inf")
	dist = [inf for i in range(n+1)]
	dist[s] = 0
	for i in range(1,n+1):
		for j,k,c in x:
			if j!=inf and dist[k]>dist[j]+c:
				dist[k] = dist[j]+c
				if i==n and k==n: return -1
	return dist
n,m = (int(i) for i in input().split())
x = []
for _ in range(m):
	i,j,k = (int(l) for l in input().split())
	x.append([i,j,-k])
b = BellmanFord(x,n,1)
if b==-1: print("inf")
else: print(-b[n])

Submission status: Accepted

Solution code:
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))
point = [None] * N
point[0] = 0
for i in range((N*4)//3):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(5):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

N,M=map(int,input().split())
V=defaultdict(int)
for i in range(M):
  a,b,c=map(int,input().split())
  V[(a-1,b-1)]=-c
d=[float('inf') for x in range(N)]

def Bellman_Ford(s):
  d[s]=0
  for i in range(N-1):
    update=False
    for ft,c in V.items():
      frm,to=ft
      if d[frm]!=float('inf') and d[to]>d[frm]+c:
        d[to]=d[frm]+c
        update=True
    if not(update):
      break
  
def Bellma_Ford_rep(n):
  upd=[False for x in range(N)]
  for i in range(N):
    update=False
    for ft,c in V.items():
      frm,to=ft
      if d[to]>d[frm]+c or upd[frm]:
        update=True
        upd[to]=True
    if not(update):
      break
  return upd[n]

Bellman_Ford(0)
if Bellma_Ford_rep(N-1):
  print("inf")
else:
  print(-d[N-1])

Submission status: Accepted

Solution code:
# from math import inf
inf = 10**50

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[v] < d[u] + w) and (d[u] != -inf):
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for i in range(N):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[u] + w > d[v]) and (d[u] != -inf):
            d[v] = d[u] + w
            if v == N-1:
                positive_loop = True
                break
    if positive_loop:
        break

if positive_loop:
    print("inf")
else:
    print(d[N-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
b = []
c = []

for _ in range(m):
	INPUT = list(map(int, input().split()))
	a.append(INPUT[0])
	b.append(INPUT[1])
	c.append(-INPUT[2])

dist = [float("inf") for _ in range(n)]
dist[0] = 0

for _ in range(1, n):
	for j in range(m):
		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]

for j in range(m):
	if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
		dist[b[j] - 1] = dist[a[j] - 1] + c[j]

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
b = []
c = []

for _ in range(m):
	INPUT = list(map(int, input().split()))
	a.append(INPUT[0])
	b.append(INPUT[1])
	c.append(-INPUT[2])

dist = [float("inf") for _ in range(n)]
dist[0] = 0

for _ in range(1, n):
	for j in range(m):
		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]

for j in range(m):
	if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
		dist[b[j] - 1] = dist[a[j] - 1] + c[j]

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

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

x = [float('-inf')] * (n+1)
x[1] = 0

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print(x[n])

Submission status: Accepted

Solution code:
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

x = [float('-inf')] * (n+1)
x[1] = 0

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

xcp = [i for i in x]
prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print(x[n])

Submission status: Accepted

Solution code:
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

x = [float('-inf')] * (n+1)
x[1] = 0

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

xcp = deepcopy(x)
prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print(x[n])

Submission status: Accepted

Solution code:
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

x = [float('-inf')] * (n+1)
x[1] = 0

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print(x[n])

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy

n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

x = [float('-inf')] * (n+1)
x[1] = 0
border = sys.maxsize // 1000

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)
        if x[b] >= border:
            x[b] = float('inf')

prevxn = x[n]
for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

if prevxn != x[n]:
    print('inf')
else:
    print(x[n])

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
li,lis,lisa = [],[],[]

for o in range(m):
    a,b,c = list(map(int, input().split()))
    li.append(a)
    lis.append(b)
    lisa.append(c)

cou = [-float('inf') for i in range(n + 1)]
cou[1] = 0
key = True
for i in range(n - 1):
    for k in range(m):
        cou[lis[k]] = max(cou[lis[k]], cou[li[k]] + lisa[k])

co = cou[n]

def ans():
    for l in range(m):
        cou[lis[l]] = max(cou[lis[l]], cou[li[l]] + lisa[l])
    if cou[n] > co:
        return 'inf'
    return cou[n]

print(ans())

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
INF = float('inf')
es = [tuple(map(int,input().split())) for i in range(M)]

ds = [INF] * N
ds[0] = 0

for i in range(N):
    for a,b,c in es:
        a,b,c = a-1,b-1,-c
        if ds[a] != INF and ds[b] > ds[a] + c:
            ds[b] = ds[a] + c
            if i == N-1 and b == N-1:
                print('inf')
                exit()
print(-ds[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E = inpl()
 
edges = [inpl() for _ in range(E)]
 
def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [-INF]*(V+1)
    D[r] = 0
#    if V == 1: # 今回は常にV>=2
#        return False, [0]
    
    for _ in range(V): # 最長でも1からNへの移動はN-1回
        update = False
        for s, t, d in edges:
            if D[t] < D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        NEGs = [False]*(V+1)
        for s, t, d in edges:
            if D[t] < D[s] + d:
                D[t] = D[s] + d
                NEGs[t] = True
                NEGs[s] = True
        return True, D, NEGs
                
    return False, D, [False]*(V+1)
  
isNEGATIVE, D, NEGs = belman_ford(V, edges, 1)
 
"""
3 = 4 < 1 > 5 なら閉路があっても問題なし 
"""   
if NEGs[-1]:
    print("inf")
else:
    print(D[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = []
for i in range(M):
    a, b, c = map(int, input().split())
    edge.append([a, b, c*-1])
d = [float('inf')] * (N+1)
d[1] = 0

for i in range(1, N+1):
    for e in edge:
        if (d[e[0]] != float('inf')) & (d[e[1]] > d[e[0]] + e[2]):
            d[e[1]] = d[e[0]] + e[2]
            update = True
            if (i == N) & (e[1] == N):
                print('inf')
                exit()

print(d[N]*-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b, c = [None] * M, [None] * M, [None] * M
INF = 1e14
d = [-INF] * N
d[0] = 0
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

for i in range(N):
    for j in range(M):
        if d[a[j]] + c[j] > d[b[j]]:
            d[b[j]] = d[a[j]] + c[j]
ans = d[N-1]
for i in range(N):
    for j in range(M):
        if d[a[j]] + c[j] > d[b[j]]:
            d[b[j]] = d[a[j]] + c[j]
if ans != d[N-1]:
    print('inf')
else:
    print(ans)

Submission status: Accepted

Solution code:
def d_ScoreAttack(N, M, R):
    INF = float('inf')
    # ベルマン-フォード法
    dist = [INF] * N
    dist[0] = 0
    # 解説におけるdistとnegativeの更新を一度に行う
    for i in range(N):
        for a, b, cost in R:
            u, v, c = a - 1, b - 1, -cost
            if dist[u] != INF and dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                if i == N - 1 and v == N - 1:
                    # この条件が満たされたとき、頂点1と頂点Nのパスの中に負閉路があった
                    # このループを使ってスコアをいくらでも大きくできる
                    return 'inf'
    return -dist[-1]

N,M = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(M)]
print(d_ScoreAttack(N, M, R))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a, b, c = [0] * M, [0] * M, [0] * M
INF = int(1e13) + 1
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

d = [-INF] * N
d[0] = 0
for __x in range(N-1):
    for i in range(M):
        if d[b[i]] < d[a[i]] + c[i]:
            d[b[i]] = d[a[i]] + c[i]

isCycle = False
for __x in range(N-1):
    if isCycle:
        break
    for i in range(M):
        if d[b[i]] < d[a[i]] + c[i]:
            d[b[i]] = d[a[i]] + c[i]
            if b[i] == N-1:
                isCycle = True
                break

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

Submission status: Accepted

Solution code:
import sys
N,M=map(int,raw_input().split())
a=[]
for i in range(M):
	x,y,z=map(int,raw_input().split())
	a.append((x,y,-1*z))

#print a

#distance
x=[ float("inf") for _ in range(N+1)]
#Set start point value to zero. 
x[1]=0


#Bellman-Ford
for h in range(N):
	for fr,to,cost in a:
		x[to]=min(x[to],x[fr]+cost)


#Judge inf
for h in range(N):
	for fr,to,cost in a:
		if x[to]>x[fr]+cost:
			x[to]=min(x[to],x[fr]+cost)			
			if to==N:
				print "inf"
				sys.exit()
			
print -1*x[N]

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

inf = float('inf')

def bellman_ford():
    for i in range(N):
        d[i] = inf
    d[0] = 0
    for i in range(N):
        for j in range(M):
            s, t, c = es[j]
            if d[s] != inf and d[t] > d[s] + c:
                d[t] = d[s] + c
    return -d[N - 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))

d = [0] * N
ans = bellman_ford()
negative = [False] * N
for i in range(N):
    for j in range(M):
        s, t, c = es[j]
        if d[s] != inf and d[t] > d[s] + c or negative[s]:
            negative[t] = True

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

Submission status: Accepted

Solution code:
N, M = [int(n) for n in input().split()]
edges = []
for m in range(M):
  a, b, c = [int(w) for w in input().split()]
  a -= 1
  b -= 1
  edges.append((a, b, c * (-1)))

inf = 10000000000000000
dist =[inf]*N
dist[0] = 0

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

ans = dist[N-1]

negative = [inf] * N
negative[0] = 0
for i in range(N):
  for a, b, c in edges:
    negative[b] = min(negative[b], negative[a] + c)

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

Submission status: Accepted

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

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

# ベルマン-フォード法
INF = float('inf')
cost = [-INF for i in range(N)]
cost[0] = 0
prev = [None for i in range(N)]

for i in range(N):
    for v in [v for v in range(N) if cost[v] != -INF]:
        for v2, c in adj[v]:
            if cost[v2] < cost[v] + c:
                cost[v2] = cost[v] + c
                prev[v2] = v

v = N - 1
for i in range(N):
    v = prev[v]
    if v == None:
        print(cost[N - 1])
        break
else:
    print('inf')

Submission status: Accepted

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

INF = float('inf')
def solve():
    d = [INF for i in range(N)]
    d[0] = 0
    for i in range(N):
        for fr,to,cost in es:
            if d[fr] == INF: continue
            if d[to] > d[fr] + cost:
                d[to] = d[fr] + cost
                if i == N-1 and to == N-1: return 'inf'
    return -d[N-1]

print(solve())

Submission status: Accepted

Solution code:
import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        #flag = False
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                #flag = True
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

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

print(ans)

Submission status: Accepted

Solution code:
import sys 

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

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf] * N
dist[0] = 0

for loop in range(N):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]
            if loop == N - 1 and b_list[i] == N:
                print('inf')
                sys.exit()

print(-dist[N-1])

Submission status: Accepted

Solution code:
def bf(edges, start, N):
    INF = float('inf')
    costs = [INF] * N
    costs[start] = 0
    for i in range(N):
        for f, t, c in edges:
            if costs[f] != INF and costs[f] + c < costs[t]:
                costs[t] = costs[f] + c
                if i == N-1 and t == N-1:
                    return 'inf'
    return -costs[N-1]

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

print(bf(edges, 0, N))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import count



def bellman_ford(edges, start_node, node_size):
    INF = float("inf")
    cost_table = [INF] * node_size
    cost_table[start_node] = 0
    for i in range(node_size):
        for f, t, c in edges:
            if cost_table[f] != INF and cost_table[f] + c < cost_table[t]:
                cost_table[t] = cost_table[f] + c

    negative = [False] * node_size
    for i in range(node_size):
        for f, t, c in edges:
            if cost_table[f] != INF and cost_table[f] + c < cost_table[t]:
                cost_table[t] = cost_table[f] + c
                negative[t] = True

            if negative[f]:
                negative[t] = True

    if negative[-1]:
        return "inf"
    else:
        return -cost_table[-1]



def main():
    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))
    print(bellman_ford(edges, 0, N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

routes = list()
for i in range(M):
    routes.append(list(map(int,input().split())))

score = [0,0] + [10**13] * (N-1)
negative = [False] * (N+1)

for i in range(N-1):
    for a,b,c in routes:
        if(score[b] > score[a] - c):
            score[b] = score[a] - c

ans = -score[N]
            
for i in range(N):
    for a,b,c in routes:
        if(score[b] > score[a] - c):
            score[b] = score[a] - c
            negative[b] = True
        if(negative[a] == True):
            negative[b] = True

if(negative[N] == True):
    print("inf")
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

n, m = map(int, input().split())
weights = {}
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    weights[(a, b)] = c

score = [-10 ** 50] * n
score[0] = 0
pred = [-1] * n
for i in range(n):
    for edge, c in weights.items():
        a, b = edge
        if score[b] < score[a] + c:
            score[b] = score[a] + c
            pred[b] = a
res = score[n - 1]

b = n - 1
while b != 0:
    a = pred[b]
    c = weights[(a, b)]
    if score[b] < score[a] + c:
        res = 'inf'
        break
    b = a

print(res)

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

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

score = [-10 ** 50] * n
score[0] = 0
for i in range(n):
    for a, b, c in edges:
        if score[b] < score[a] + c:
            score[b] = score[a] + c
res = score[n - 1]

for i in range(n):
    for a, b, c in edges:
        if score[b] < score[a] + c:
            score[b] = score[a] + c
if res < score[n - 1]:
    res = 'inf'
print(res)

Submission status: Accepted

Solution code:

inf = 10 ** 20


def solve(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    b = n - 1
    while b != 0:
        a = pred[b]
        c = weights[(a, b)]
        if score[b] < score[a] + c:
            return 'inf'
        b = a
    return score[n-1]


def solve2(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    res = score[n-1]

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    if res < score[n-1]:
        return 'inf'
    return res


def main():
    n, m = map(int, input().split())
    weights = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        weights[(a, b)] = c

    res = solve2(n, m, weights)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')

inf = 10 ** 20


def solve(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    b = n - 1
    while b != 0:
        a = pred[b]
        c = weights[(a, b)]
        if score[b] < score[a] + c:
            return 'inf'
        b = a
    return score[n-1]


def solve2(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    res = score[n-1]

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    if res < score[n-1]:
        return 'inf'
    return res


def main():
    n, m = map(int, input().split())
    weights = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        weights[(a, b)] = c

    res = solve(n, m, weights)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

NINF = float('-inf')
dists = [NINF for _ in range(n)]
dists[0] = 0


def trace(v, updated):
    updated[v] = True
    for b, c in edges[v]:
        if not updated[b]:
            trace(b, updated)


def bellman_ford():
    for i in range(n - 1):
        updated = False
        for j in range(n):
            dj = dists[j]
            if dj == NINF:
                continue
            for b, c in edges[j]:
                if dists[b] >= dj + c:
                    continue
                dists[b] = dj + c
                updated = True
        if not updated:
            return dists[-1]

    n_updated = [False] * n
    for j in range(n):
        if n_updated[j]:
            continue
        dj = dists[j]
        if dj == NINF:
            continue
        for b, c in edges[j]:
            if dists[b] < dj + c:
                trace(b, n_updated)

    return 'inf' if n_updated[-1] else dists[-1]


print(bellman_ford())