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:
inf = float('inf')

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

e = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s -= 1
    t -= 1
    c *= -1
    e.append((s, t, c))

dist = [inf] * n
dist[0] = 0
ans = None
for cnt in range(n * 2):
    for s, t, c in e:
        if dist[s] != inf and dist[t] > dist[s] + c:
            dist[t] = dist[s] + c
            update = True
    if cnt == n - 1:
        ans = -dist[n - 1]
if ans != -dist[n - 1]:
    print('inf')
else:
    print(ans)

# 「ベルマンフォード法」の pythonのコード
# (https://juppy.hatenablog.com/entry/2018/10/30/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E9%96%A2%E9%80%A3_python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)
#
# Bellman Fordは負辺があってもかまわない場合の単一始点全点間最短距離を求め，同時に負閉路の存在を検出するアルゴリズムである．
#
# これは動的計画法に基づくアルゴリズムで，k 回目の更新によって始点から k ステップ以下で進む場合の最短距離が計算される．
# もし n 回目にもまだ更新があるのならば，経路はどこかに負の閉路を含んでいるので，
# その頂点への経路には負閉路が存在するとして距離を負の無限大に設定する．
# (http://www.prefield.com/algorithm/graph/bellman_ford.html)
#
# 通常の Bellman-Ford 法における負閉路検出は、後者の負閉路に対して「負閉路あり」と判定してしまうことに注意。それを防ぐためには、
# 本来 Bellman-Ford は N-1 回のイテレーションで終わるので N 回目以降にも更新が行われたら負閉路ありとしていたところを
# N 回目以降にも頂点 N への最短路が更新されたら、「1 から N までの間に負閉路あり」
# と判定すればいい。この場合、ループは 2N 回程度回せば確実。
# (http://drken1215.hatenablog.com/entry/2019/02/16/075900)

Submission status: Accepted

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

dist[0] = 0

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

ans = dist[N-1]

nega = [0] * N

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
E=[]
for i in range(m):
    a,b,c=map(int,input().split())
    E.append((a-1,b-1,c))
INF=-10**20
score=[INF]*n
score[0]=0
for i in range(n-1):
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]<score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
negative=[False]*n
for i in range(n):
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]<score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
                negative[e[1]]=True
if negative[n-1]:
    print('inf')
else:
    print(score[n-1])

Submission status: Accepted

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

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

INF = float("inf")
d = [INF] * N # 頂点１からの最短距離
d[0] = 0

for i in range(N):
    for f, t, c in es:
        f, t = f-1, t-1
        c = c * -1 # ここで負にしておくと最小経路を選んだ時に絶対値としては最大になるので最後にマイナスをかけて出せばよい
        if d[f] != INF and d[t] > d[f] + c: # fromまで到達できる、かつ、toまでのコストがfromまでのコスト＋from->toのコストより大きいとき
            d[t] = d[f] + c
            if i == N-1 and t == N-1: #N回目の更新でそれでも頂点Nが更新された→負の閉路がある
                print("inf")
                exit()

print(-d[-1])

Submission status: Accepted

Solution code:
from sys import stdin

INF = float('inf')


def bellman_ford(n, edges, r):
    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]


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]

    Edges = [None] * M

    for i in range(M):
        ai, bi, ci = [int(x) for x in stdin.readline().rstrip().split()]
        Edges[i] = (ai-1, bi-1, -ci)

    ans = bellman_ford(N, Edges, 0)

    print(ans)


if __name__ == '__main__':
    main()

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):
        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, 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 ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def BF(E,s,n):
  inf=float("inf")
  d=[inf for _ in range(n)]
  d[s]=0
  for i in range(n+1):
    for e in E:
      if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
        d[e[1]-1] = d[e[0]-1] + e[2]
    if i==n-1:t=d[-1]
    if i==n and t!=d[-1]:
      return 'loop'
  return d

def main():
  N,M = II()
  E = []
  for _ in range(M):
    a,b,c = II()
    E.append([a,b,-c])

  d = BF(E,0,N)

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def BF(E,s,n):
  inf=float("inf")
  d=[inf for _ in range(n)]
  d[s]=0
  for i in range(n+1):
    for e in E:
      if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
        d[e[1]-1] = d[e[0]-1] + e[2]
    if i==n-1:t=d[-1]
    if i==n and t!=d[-1]:
      return 'loop'
  return d

N,M = II()
E = []
for i in range(M):
  a,b,c = II()
  E.append([a,b,-c])

d = BF(E,0,N)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    print(a)
else:
    print("inf")

Submission status: Accepted

Solution code:
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def remove_Edge(N,Ef,Eb,start,goal):
    v = connect_dfs(N,Ef,start) & connect_dfs(N,Eb,goal)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            Ef[j].pop(i)

def Bellman_Ford(N,E,start,INFTY=10**18):
    def update(dist,N,E,start):
        done = [False]*N
        done[start] = True
        q = [start]
        d = dist[:]
        while q:
            i = q.pop()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    q.append(j)
                    done[j] = True
        return d
    #
    d = [INFTY]*N
    d[start] = 0
    for _ in range(N-1):
        d = update(d,N,E,start)
    if d!=update(d,N,E,start):
        return None
    else:
        return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]
    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    
    remove_Edge(N,E,Eb,0,N-1)
    d = Bellman_Ford(N,E,0)
    if d == None:
        print("inf")
    else:
        print(-d[-1])
    
main()

Submission status: Accepted

Solution code:
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def update(dist,N,E,start):
    done = [False]*N
    done[start] = True
    q = [start]
    d = dist[:]
    while q:
        i = q.pop()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                q.append(j)
                done[j] = True
    return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    v = connect_dfs(N,E,0) & connect_dfs(N,Eb,N-1)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    for _ in range(N-1):
        d = update(d,N,E,0)
    if d!=update(d,N,E,0):
        print("inf")
    else:
        print(-d[-1])

main()

Submission status: Accepted

Solution code:
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = -c

    #0 -> N-1 経路上にない頂点を除く
    V1 = [False]*N
    V1[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        for j in E[i]:
            if V1[j]:continue
            qa(j)
            V1[j]=True
    V2 = [False]*N
    V2[-1] = True
    qa(N-1)
    while q:
        i = qp()
        for j in Eb[i]:
            if V2[j] or not V1[j]:continue
            qa(j)
            V2[j]=True
    for i in range(N):
        if V1[i] and V2[i]:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    def update():
        done = [False]*N
        done[0] = True
        q = [0]
        qp = q.pop
        qa = q.append
        while q:
            i = qp()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    qa(j)
                    done[j] = True

    for _ in range(N-1):update()
    dc = d[:]
    update()
    if dc!=d:
        print("inf")
    else:
        print(-d[-1])
main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c
    Eb[b-1][a-1] = -c

#0 -> N-1 経路上にない頂点を除く
V1 = [False]*N
V1[0] = True
q = [0]
qp = q.pop
qa = q.append
while q:
    i = qp()
    for j in E[i]:
        if V1[j]:continue
        qa(j)
        V1[j]=True
V2 = [False]*N
V2[-1] = True
qa(N-1)
while q:
    i = qp()
    for j in Eb[i]:
        if V2[j] or not V1[j]:continue
        qa(j)
        V2[j]=True
for i in range(N):
    if V1[i] and V2[i]:continue
    for j in Eb[i]:
        E[j].pop(i)

INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True
                
for _ in range(N-1):update()
dc = d[:]
update()
if dc!=d:
    print("inf")
else:
    print(-d[-1])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    g = []
    INF = 10 ** 9 * 1000
    d = [INF] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != INF and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print(-d[-1])


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    g = []
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != float('INF') and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print(-d[-1])


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        c = -c
        g[a].append((b, c))
    for i in range(2 * N):
        for x, r in enumerate(g):
            for y, c in r:
                if d[x] != float('INF') and d[y] > d[x] + c:
                    d[y] = d[x] + c
                    if y == N and i > N:
                        print("inf")
                        exit()

    print(-d[-1])


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    INF = -1 * 10 ** 9 * 1000
    d = [INF] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        g[a].append((b, c))
    for i in range(2 * N):
        for x, r in enumerate(g):
            for y, c in r:
                if d[x] != INF and d[x] + c > d[y]:
                    d[y] = d[x] + c
                    if y == N and i > N:
                        print("inf")
                        exit()

    print(d[-1])


main()

Submission status: Accepted

Solution code:

N,M = list(map(int,input().split(" ")))
INF = -(10 ** 20)
graph = [ INF for _ in range(N + 1)]
edges = []
for _ in range(M):
    a,b,c = list(map(int,input().split(" ")))
    edges.append((a,b,c))

graph[1] = 0
for i in range(2 * N): #ループがなければ更新は N - 1回 以降行われない
    for edge in edges:
        fr,to,point = edge
        if graph[fr] + point >  graph[to] and  graph[fr] != INF:
            graph[to] = graph[fr] + point
            if to == N and i > N:
                print("inf")
                exit()

print(graph[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# from collections import defaultdict
def main():
    N, M = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = 10**14
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    if ans == V[N-1]:
        print(-ans)
    else:
        print("inf")
        
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())
    edges.append([a,b,c])

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

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

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    node_num, edge_num = map(int, input().split())
    graph_data = [list(map(int, input().split())) for i in range(edge_num)]
    inf = -10 ** 15
    length_data = [inf for i in range(node_num + 1)]
    length_data[1] = 0

    ans_data = length_data[node_num]
    for i in range(node_num):
        for a, b, c in graph_data:
            b_lengh = length_data[a] + c
            length_data[b] = max(b_lengh, length_data[b])
        # print(length_data, b_lengh, ans_data, length_data[node_num])
        if i == node_num - 1 and length_data[node_num] > ans_data:
            ans_data = 'inf'
        else:
            ans_data = length_data[node_num]

    print(ans_data)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    [N, M] = [int(i) for i in input().split()]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen

    dist2 = dist.copy()

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist2[a-1] + c
            if newLen > dist2[b-1]:
                dist2[b-1] = newLen

    if dist[N-1] != dist2[N-1]:
        print('inf')
    else:
        print(dist[N-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    [N, M] = [int(i) for i in input().split()]
    edge = [[10**100] * N for _ in range(N)]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    flag = False

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen
        if i == N-1 and dist[N-1] > predist:
            flag = True
        predist = dist[N-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = [int(s) for s in input().split()]
dist = [N*-10**9]*N
E = []
flag = 0
change = 0
N_flag = 0
for i in range(M):
    a,b,c = [int(s) for s in input().split()]
    E.append((a,b,c))
dist[0] = 0
for i in range(N):
    for (a,b,c) in E:
        if a == N or b == N:
            N_flag = 1
        newLen = dist[a-1] + c
        if newLen > dist[b-1]:
            change = 1
            dist[b-1] = newLen
            if i == N-1 and change == 1 and N_flag == 1:
                flag = 1
        change = 0
        N_flag = 0
if flag == 1:
    print('inf')
else:
    print(dist[N-1])

Submission status: Accepted

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1 and e[1] == numNodes-1:
                        return True, d
        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_bool(0, N)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = []
for _ in range(M):
    a,b,c = map(int, input().split())
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            dist[b] = newlen
    if i == N-1 and dist[N] > predist:
        flag =True
    predist = dist[N]

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    
    for i in range(n<<1):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
        if i <= n: a0 = dist[-1]
    if a0 != dist[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = []
for _ in range(M):
    a,b,c = map(int, input().split())
    E.append((a,b,c))
dist = [-N*10**9]*(N+1)
dist[1] = 0
flag = False
for i in range(N):
    for (a,b,c) in E:
        newlen = dist[a] + c
        if newlen > dist[b]:
            if i == N-1:
                flag = True
            dist[b] = newlen
            predist = dist[N]

dist2 = dist.copy()
for i in range(N):
    for (a,b,c) in E:
        newlen = dist2[a] + c
        if newlen > dist2[b]:
            dist2[b] = newlen
if dist2[N] > dist[N]:
    print("inf")
else:
    print(dist[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import sys

sys.setrecursionlimit(100000)

def main():
    N, M = readi(2)
    edges = readi(M, 3)
    dist = arr(N + 1, fill_value=float("-inf"))
    dist[1] = 0
    for i in range(N - 1):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                dist[b] = new_d
    
    ans = dist[N]

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

    if ans != dist[N]:
        print('inf')
    else:
        print(dist[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict
import sys

sys.setrecursionlimit(100000)

def main():
    N, M = readi(2)
    edges = readi(M, 3)
    pred = defaultdict(list)
    for a, b, _ in edges:
        pred[b].append(a)
    # dbg(pred=pred)
    s = set()
    s2 = set()

    def rec(n):
        if n not in s2:
            s2.add(n)
            for m in pred[n]:
                s.add(m)
                rec(m)

    rec(N)
    # dbg(s=s)
    dist = arr(N + 1, fill_value=float("-inf"))
    dist[1] = 0
    for i in range(N):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                if i == N - 1 and b in s:
                    print("inf")
                    return
                dist[b] = new_d
    print(dist[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    negative = [False]*n
    for i in range((2*n)):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if negative[v]: negative[to] = True
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
                if i >= n:
                    negative[to] = True
        if not updated: break
    if negative[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

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

Submission status: Accepted

Solution code:
class BellmanFord():
	def __init__(self, adj, start):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		return

	#負閉路のせいでgoalへの距離が-infになるか
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for x in range(self.size):
			for y, w in self.adj[x]:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		if res != self.dist[goal]:
			return True
		else:
			return False

	def GetDistance(self, goal):
		return self.dist[goal]

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

bf = BellmanFord(adj, 0)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print("inf")
else:
	print(-bf.GetDistance(n-1))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		return

	#負閉路のせいでgoalへの距離が-infになるか
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for x in range(self.size):
			for y, w in self.adj[x]:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		if res != self.dist[goal]:
			return True
		else:
			return False

	def GetDistance(self, goal):
		return self.dist[goal]

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

bf = BellmanFord(adj, 0)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print("inf")
else:
	print(-bf.GetDistance(n-1))