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 time
time0=time.time()

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

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

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

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


from collections import deque

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

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

SCORE[1]=0

QUE=deque([1])

while QUE:

    x=QUE.pop()

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

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

else:
    print(SCORE[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import *
N,M=map(int,input().split())
INF=float("inf")
G=[[] for i in range(N)]
Gm=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    Gm[b].append((a,c))
O=[[0]*N for i in range(N)]
stack=[g for g in Gm[N-1]]
reached=[0]*N
reached[N-1]=1
while(stack):
    a,c=stack.pop()
    reached[a]=1
    for i,j in Gm[a]:
        if reached[i]==0:
            stack.append((i,j))
R=[False]*N
R[0]=0
stack=[(-i[1],0,i[0]) for i in G[0] if reached[i[0]]==1]
heapify(stack)
while(stack):
    c,a,b=heappop(stack)
    c=-c
    if R[b]==False:
        O[a][b]=1
        R[b]=c
        for i in G[b]:
            if reached[i[0]]==1:
                heappush(stack,(-i[1]-c,b,i[0]))
    if R[b]!=False and R[b]<c:
        if O[a][b]==1:
            print("inf")
            quit()
        else:
            R[b]=c
            O[a][b]=1
            for i in G[b]:
                if reached[i[0]]==1:
                    heappush(stack,(-i[1]-c,b,i[0]))

print(R[N-1])

Submission status: Accepted

Solution code:
INF = float("inf")
n, m = map(int, input().split())
edges = [None] * m

# n:node num
# e:edges
# s:start node

d = [INF] * n
d[0] = 0
def Bellmanford(n, e, s):

    # 経路は最大でもN-1回移動すると終わるので（閉路がない限り）その分だけ更新
    for i in range(n):
        # すべての辺についてみていく
        for a,b,c in e:
            # aにたどり着ける（コストがINFではない）かつ、今のところのbまでのコストがa->bで行くときより大きい場合、更新
            if d[a] != INF and d[a] + c < d[b]:
                d[b] = d[a] + c

                # N回目更新した際に、それでも最終地点Nまでのコストが更新されたー＞負の閉路がある
                if i == n-1 and b == n-1:
                    return INF


    return -1 * d[-1]



for i in range(m):
    A, B, C = map(int, input().split())
    edges[i] = (A-1, B-1, -C)

ans = Bellmanford(n, edges, 0)
print(ans)

Submission status: Accepted

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

# 求めたい経路の外の閉路にはまるとまずい
#graph = csr_matrix((val,(row,col)),(N+1,N+1))
#try:
#  dist = bellman_ford(graph,indices = [1])[0].astype(int)
#  answer = -dist[N]
#except:
#  answer = 'inf'
import numpy as np
from scipy.sparse.csgraph import connected_components

graph = csr_matrix((val,(row,col)),(N+1,N+1))

find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
_,labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1])

# 強連結成分に制限。ここに負閉路があれば～～
graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Accepted

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

# 求めたい経路の外の閉路にはまるとまずい
#graph = csr_matrix((val,(row,col)),(N+1,N+1))
#try:
#  dist = bellman_ford(graph,indices = [1])[0].astype(int)
#  answer = -dist[N]
#except:
#  answer = 'inf'
import numpy as np
from scipy.sparse.csgraph import connected_components

graph = csr_matrix((val,(row,col)),(N+1,N+1))

find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
_,labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1])

graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float('inf')
def Bellmanford(n, edges, r):#r->start
    d = [INF] * n
    d[r] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    return -d[n-1]


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

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

dist = [inf]*n
dist[0] = 0
for i in range(1,n):
    for j in range(m):
        if dist[edge[j][1]] > dist[edge[j][0]]+edge[j][2]:
            dist[edge[j][1]] = dist[edge[j][0]]+edge[j][2]

ans = dist[n-1]

for j in range(m):
    if dist[edge[j][1]] > dist[edge[j][0]]+edge[j][2]:
        dist[edge[j][1]] = dist[edge[j][0]]+edge[j][2]
if dist[n-1]<ans:
    print("inf")
else:
    print(-ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

dist = [inf]*n
dist[0] = 0
for i in range(1,n):
    for j in range(m):
        if dist[edge[j][1]-1] > dist[edge[j][0]-1]+edge[j][2]:
            dist[edge[j][1]-1] = dist[edge[j][0]-1]+edge[j][2]

ans = dist[n-1]

for j in range(m):
    if dist[edge[j][1]-1] > dist[edge[j][0]-1]+edge[j][2]:
        dist[edge[j][1]-1] = dist[edge[j][0]-1]+edge[j][2]
if dist[n-1]<ans:
    print("inf")
else:
    print(-ans)

Submission status: Accepted

Solution code:
def bellmanford(v,e,s,path):
    inf = float('inf')
    d = [inf for i in range(v)]
    d[s] = 0
    for j in range(v):
        update = False
        for i in range(e):
            if d[path[i][0]] != inf and d[path[i][1]] > d[path[i][0]] + path[i][2]:
                d[path[i][1]] = d[path[i][0]] + path[i][2]
                update = True
                if j == v-1 and path[i][1]==n-1:
                    return -1
        if not update:
            break
    return d


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

path = []

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

d = bellmanford(n,m,0,path)

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

Submission status: Accepted

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

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

edges = ABC[:]
NUM_V = N+1 # 番号0のエッジを簡単のため追加

# 最短経路に置き換えるためコストに-1をかける
edges = [(a,b,-1*c) for a,b,c in edges]


# ベルマンフォード
import sys
INT_MAX = sys.maxsize # 9223372036854775807

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    #辺の緩和
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist

longest = bellman_ford(edges, NUM_V, 1)
ans_value = -1 * longest[NUM_V - 1]
if ans_value == INT_MAX:
    print('inf')
else:
    print(ans_value)

Submission status: Accepted

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

dw = [ [] for i in range(N) ]


for a,b,c in li:
  dw[a].append( (b,c) )

NOT = 1e+16 -1 
  
cost = [NOT]*N
cost[0]=0
cosli = []
for i in range(1000):
  chk = [0]*N
  now = 0
  pop=[now]
  for i in range(N):
    if (len(pop)==0):
      break
    now = pop.pop()
    chk[now]=1
    for b,c in dw[now]:
      if ( cost[b] == NOT ):
        cost[b] = cost[now] + c
      else:
        cost[b] = max(cost[now] + c,cost[b])
      if (chk[b]==0):
        pop.append(b)
  cosli.append( cost[N-1] )  

if ( cosli[-1] != cosli[-2] ):
  print ("inf")
else:
  print (cosli[-1])

Submission status: Accepted

Solution code:
from collections import deque


n, m = map(int, input().split())
tree = [[] for i in range(n)]
path = {}
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tree[tmp1-1].append([tmp2-1, cost])

q = deque()
q.append([-1, 0])
pos_cost = [-float("inf")]*n
pos_cost[0] = 0
path = {}

def judge(start):
    q2 = deque()
    q2.append(start)
    visited = [False]*n
    visited[start] = True
    while q2:
        pos = q2.popleft()
        for next_pos, cost in tree[pos]:
            if not visited[next_pos]:
                q2.append(next_pos)
                visited[next_pos] = True
    if visited[n-1]:
        print("inf")
        exit()

while q:
    prev_pos, pos = q.popleft()
    if prev_pos*10000 + pos in path:
        judge(pos)
        continue
    path[prev_pos*10000 + pos] = 1
    for next_pos, cost in tree[pos]:
        if pos_cost[pos] + cost > pos_cost[next_pos]:
            pos_cost[next_pos] = pos_cost[pos] + cost
            q.append([pos, next_pos])
print(pos_cost[n-1])

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d

# coding: utf-8
# Your code here!

#input_template
inpPh = 3
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    pass
 
   # print(f'selected_input({inpPh}):\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M = tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,-ci))

vlist =[ None for _ in range(N)]    

        
s_loc,g_loc = 0, N-1

vlist[s_loc] = 0
#print(vlist)




is_inf = False
for i in range(len(vlist)):
    for e in elist:
        a,b,c = e
        if vlist[a] == None:
            continue
        elif vlist[b] == None or vlist[b] > vlist[a] + c:
            vlist[b] = vlist[a] + c
            if i == N-1 and b == N-1:
                pass
                is_inf = True
                 
res = -vlist[g_loc]            


if is_inf:
    print('inf')
else:
    print(res)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

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

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)

#graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1
try:
    d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
    print(-int(d1[0][0]))
except:
    print("inf")

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N,M = map(int,input().split())
ways = []
for i in range(M):
    way = [int(i) for i in input().split()]
    ways.append(way)

ways.sort()
dp = [None for i in range(N+1)]

dp[1] = 0
cnt_way = 0
for j in range(N+1):
    for i in range(M):
        a,b,c = ways[i]
        if dp[a] != None:
            if dp[b] == None:
                dp[b] = dp[a] + c
            else:
                dp[b] = max(dp[b],dp[a]+c)

    if j == N-1:
        ans = dp[-1]

if ans == dp[-1]:
    pass
elif ans < dp[-1]:
    ans = "inf"

print(ans)

Submission status: Accepted

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

for i in range(N):
    d_N = d[N]
    for j in range(M):
        a = data[j][0]
        b = data[j][1]
        c = data[j][2]
        d[b] = max(d[b], d[a]+c)
    if i == N-1:
        if d_N != d[N]:
            ans = "inf"
        else:
            ans = d[N]
print(ans)

Submission status: Accepted

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

inf = float('inf')

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    
    next_v = [[] for v in V]
    for i in range(M):
        next_v[a[i]-1].append((b[i]-1, c[i]))
    
    D = [-inf for v in V]
    D[0] = 0
    
    prev = [None for v in V]

    positive = [False for v in V]

    for i in range(N-1):
        for u in V:
            for v, w in next_v[u]:
                alt = D[u] + w
                if alt > D[v]:
                    D[v] = alt
                    prev[v] = u
    ans = D[N-1]
    
    for i in range(N-1):
        for u in V:
            for v, w in next_v[u]:
                alt = D[u] + w
                if alt > D[v]:
                    D[v] = alt
                    positive[v] = True
                if positive[u]:
                    positive[v] = True

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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    c = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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(float('inf'))
                exit()

print(-dist[N - 1])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
edge = []
c = []
ed_list = [[] for _ in range(n)]
for i in range(m):
    t_a, t_b, t_c = map(int,input().split())
    edge.append([t_a - 1,  t_b - 1])
    c.append(-t_c)
    ed_list[t_a - 1].append(t_b - 1)

INF = float('inf')
score = [INF for _ in range(n)]
score[0] = 0
for i in range(n):
    for u, cost in zip(edge, c):
        if score[u[1]] > score[u[0]] + cost:
            score[u[1]] = score[u[0]] + cost
ans = score[n-1]
for i in range(n):
    for u, cost in zip(edge, c):
        if score[u[1]] > score[u[0]] + cost:
            score[u[1]] = score[u[0]] + cost
print(-ans if ans == score[n-1] else 'inf')

Submission status: Accepted

Solution code:
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())
 
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
#print(d)

def BELLMANFORD(point,d):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1

    return cost,negative

x,y=(BELLMANFORD(1,d))
#print(x,y)
if y[n-1]==1:
    print("inf")
else:
    print(x[n])

Submission status: Accepted

Solution code:
n, m = [int(item) for item in input().split()]
edge = []
inf =  2000 * 10**10
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    edge.append([a-1, b-1, -c])

def BellmanFord(start):
    dist = [inf for i in range(n)]
    dist[0] = 0
    for i in range(n):
        for u, v, c in edge:
            if dist[u] != inf and (dist[u] + c) < dist[v]:
                dist[v] = dist[u] + c
                if i == n-1 and v == n-1:
                    return "inf"
    return -dist[-1]

ret = BellmanFord(0)
print(ret)

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 初期値用:十分小さい数(-100億)
    # -INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [INF]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if math.isinf(d[a[i]-1]):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[b[i]-1]+=1
                update=True
        if not update:
            break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    # negative = [False]*N
    # for j in range(N):
    #     for i in range(M):
    #         if(d[a[i]-1] == 1e10):
    #             continue
    #         if(d[b[i]-1] > d[a[i]-1]+c[i]):
    #             d[b[i]-1] = d[a[i]-1]+c[i]
    #             negative[b[i]-1] = True
    #         if(negative[a[i]-1]):
    #             negative[b[i]-1] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#コストをマイナスにして最小化する
import sys
inf=10**15
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
cost=[inf]*N
cost[0]=0
abc=[[int(o) for o in fastinput().split()] for _ in range(M)]#[a,b,c];点a-1とb-1を結ぶ辺のコストが-c
for t in range(N):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1#コストの更新あり
            cost[b-1]=cost[a-1]-c
gendankainokosuto=cost[N-1]
for t in range(100):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1#コストの更新あり
            cost[b-1]=cost[a-1]-c
if cost[N-1]!=gendankainokosuto:
    print("inf")
else:
    print(-cost[N-1])

Submission status: Accepted

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(n):
        for edge in edges:
            if 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:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return int(-dist[N-1])


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

Submission status: Accepted

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1 and abci[1]==n-1:
                print('inf')
                exit()

print(-d[n-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

# 隣接リストを作成(key:b, val:a)
edges = []
for _ in range(m):
    ai, bi, ci = li()
    ai -= 1
    bi -= 1
    edges.append((ai, bi, ci))

# ベルマンフォード
dist = [[-10**18]*n for _ in range(2*n+3)]
for i in range(2*n+2):
    dist[i][0] = 0

ans = -10**18
chk = -10**18

for i in range(2*n+2):
    for ai, bi, ci in edges:
        dist[i+1][bi] = max(dist[i+1][bi],
                            dist[i][bi],
                            dist[i][ai] + ci)
    if i == n:
        ans = dist[i][n-1]
        
    elif i == 2*n+1:
        chk = dist[i][n-1]
        
print(ans if ans >= chk else "inf")

Submission status: Accepted

Solution code:
def bellman_ford(vertex_num: int, edges: list, source: int, sink: int) -> list:
    # 1) initialize distance
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    # 2) update distances (upto vertex_num-1 times)
    for _ in range(vertex_num):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    # 3) detect negative-loop
    for u, v, c in edges:
        if distances[u] + c < distances[v]:
            distances[v] = distances[u] + c

            if v == sink:
                return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0, N-1)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

# distの初期化: dist = [inf for _ in range(N)]; dist[start] = 0
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(dist,edges,N,end):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                # 頂点数Nなら更新は高々N-1回で済む
                # N回目にendの更新を行うなら経路の中に負閉路があるということ
                if i == N-1 and nv == end:
                    return False
    return True

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

flag = bellmanford(dist,info,N,N-1)
ans = -dist[N-1] if flag else "inf"
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

# distの初期化: dist = [inf for _ in range(N)]; dist[start] = 0
# True - >正常に更新, False -> 負閉路有り
def bellmanford(dist,edges,N):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                # 頂点数Nなら更新は高々N-1回で済む
                # N回目に更新を行うなら負閉路があるということ
                if i == N-1 and nv == N-1:
                    return False
    return True

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

flag = bellmanford(dist,info,N)
ans = -dist[N-1] if flag is True else "inf"
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N,M = map(int,input().split())
info = []
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    info.append((a,b,c))
 
dist = [-inf for _ in range(N)]
dist[0] = 0
for i in range(N):
    for v,nv,w in info:
        if dist[nv] < dist[v] + w:
            dist[nv] = dist[v] + w
            if i == N-1 and nv == N-1:
                print("inf")
                exit()
ans = dist[N-1]
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[a] != -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1 and b == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Accepted

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

a = [0] * m
b = [0] * m
c = [0] * m

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

INF = (n-1) * max(abs(min(c)),abs(max(c)))

dist = [INF] * n

dist[0] = 0

for j in range(0,n-1):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        dist[b[i]] = min(dist[b[i]], dist[a[i]] + c[i])

ans = - dist[n-1]

negative = [False] * n

for j in range(0,n):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        if negative[a[i]]:
            negative[b[i]] = True
        elif dist[a[i]] + c[i] < dist[b[i]]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True

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