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:
n, m = map(int, input().split())

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

init_val = -10 ** 9 * 1000
d = [init_val] * n
d[0] = 0
for _ in range(n):
    updated = False
    for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            updated = True
    if not updated:
        break
if updated: #閉路の存在
     for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            if b == n - 1:
                print('inf')
                quit()
print(d[n-1])

Submission status: Accepted

Solution code:
# BFS
# 現在の頂点、スコア、通過した頂点の数、を状態量としてもち、2*n個まで試す
# n個より多いものが最大になるのなら'inf'を出力
from collections import deque
from sys import stdin
def input():
    return stdin.readline().strip()

inf = float('inf')

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

edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(m):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    weight[i].append(k)

seen = [-inf] * n
todo = deque([(0, 0, 1)])
while len(todo) > 0:
    node, score, num = todo.popleft()
    if num > 2 * n:
        break

    for i in range(len(edge[node])):
        if seen[edge[node][i]] < score + weight[node][i]:
            seen[edge[node][i]] = score + weight[node][i]
            todo.append((edge[node][i], score + weight[node][i], num + 1))
            if edge[node][i] == n - 1 and num >= n:
                print('inf')
                exit()

print(seen[n-1])

Submission status: Accepted

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

cost = [-float("INF")]*(N+1)
cost[1] = 0
cnt = 0
flag = True
for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

tmp = cost[N]

for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

if tmp < cost[N]:
    print("inf")
else:
    print(tmp)

Submission status: Accepted

Solution code:
INF = 10**30
import sys
sys.setrecursionlimit(10**6)
def bellman_ford(s, t, g):
    d = [INF for _ in range(n)] # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    val_at_t = INF # 下記参照
    for i in range(n):
        #update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                #update = True
        # 負閉路が存在して、点tの値が更新され続けている場合
        if i == n-1 and val_at_t > d[t]:
            return []
        val_at_t = d[t] #点tの現在の値
    return d

n, m = map(int, input().split()) # n:頂点数, m:辺の数
g = []
for _ in range(m):
    x, y, z = map(int, input().split()) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])
    
ans = bellman_ford(0, n-1, g)
#print(ans)
print(-ans[n-1] if ans else "inf")

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m = map(int,ipt().split())

    way = [[] for i in range(n+1)]
    gway = [[] for i in range(n+1)]
    rway = [[] for i in range(n+1)]
    for i in range(m):
        a,b,c = map(int,ipt().split())
        way[a].append((b,-c))
        rway[b].append(a)
        gway[a].append(b)

    ar = [True]*(n+1)
    ar[n] = False
    q = [n]
    while q:
        qi = q.pop()
        for j in rway[qi]:
            if ar[j]:
                ar[j] = False
                q.append(j)
    q = [1]
    ar2 = [True]*(n+1)
    ar2[1] = False
    while q:
        qi = q.pop()
        for j in gway[qi]:
            if ar2[j]:
                ar2[j] = False
                q.append(j)

    for i in range(1,n+1):
        if ar[i] or ar2[i]:
            way[i] = []

    def bellmanford(s,g,way):
        n = len(way)
        d = [10**18]*(n)
        d[s] = 0
        sl = 0
        re = True
        while re:
            re = False
            for i in range(1,n):
                for j,cj in way[i]:
                    if d[j] > d[i]+cj:
                         d[j] = d[i]+cj
                         re = True
            sl += 1
            if sl == n:
                d[g] = -10**18
                break
        return d[g]

    ans = bellmanford(1,n,way)
    if ans == -10**18:
        print("inf")
    else:
        print(-ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])

def bellmanFord(G,s):
  D=[INF for i in range(n)]
  D[s]=0
  for i in range(1,n):
    for x,y,z in G:
      D[y]=min(D[y],D[x]+z)
  ans=-D[n-1]
  for x,y,z in G:
    D[y]=min(D[y],D[x]+z)
  if ans!=-D[n-1]:
    return -1
  else:
    return -D[n-1]

ans=bellmanFord(G,0)
if ans==-1:
  print('inf')
else:
  print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])
  
def main():
  D=[INF for _ in range(n)]
  D[0]=0
  for i in range(n):
    for x,y,z in G:
      if D[x]!=INF and D[y]>D[x]+z:
        D[y]=D[x]+z
        if i==n-1 and y==n-1:
          return 'inf'
  return -D[n-1]
   
if __name__=='__main__':
  print(main())

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
dp = (N+1)*[float("inf")]
dp[1] = 0

for n in range(N):
  for a,b,c in E:
    dp[b] = min(dp[b],dp[a]-c)

x = dp[N]

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

if x!=dp[N]:
  print("inf")
else:
  print(-x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N,M = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
rg = defaultdict(list)
for a,b,c in abc:
    g[a].append((b,c))
    rg[b].append(a)

inf = 10**20
score = [-inf]*(N+1)
score[1] = 0

for i in range(N-1):
    for v in range(1,N+1):
        for nv, c in g[v]:
            if score[v] + c > score[nv]:
                score[nv] = score[v] + c

update = [False]*(N+1)
for v in range(1,N+1):
    for nv, c in g[v]:
        if score[v] + c > score[nv]:
            score[nv] = score[v] + c
            update[v] = True

visited = [False]*(N+1)
l = [N]
while l:
    v = l.pop()
    visited[v] = True
    for nv in rg[v]:
        if not visited[nv]:
            l.append(nv)
for u,v in zip(update, visited):
    if u and v:
        print('inf')
        exit()

print(score[N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = []
for _ in range(M):
  u, v, c = map(int, input().split())
  e.append((u, v, -c))
inf = 10 ** 18
d = [inf] * (N + 1)
d[1] = 0
for _ in range(N - 1):
  for u, v, c in e: d[v] = min(d[v], d[u] + c)
loop = []
for u, v, c in e:
  if d[v] > d[u] + c:
    d[v] = min(d[v], d[u] + c)
    loop.append(v)
if len(loop) == 0:
  print(-d[-1])
  exit(0)
for v in loop: d[v] = -inf
for _ in range(N - 1):
  for u, v, c in e:
    if v == N and (d[v] > d[u] + c): break
    d[v] = min(d[v], d[u] + c)
  else: continue
  break
else: 
  print(-d[-1])
  exit(0)
print("inf")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [None]*M
INF = 10**18

for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)
    
def bellman(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[-1]
    
ans = bellman(N, edges, 0)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, ci in G[u]:
                if dist[u] + ci > dist[v]:
                    dist[v] = dist[u] + ci
                    v_changeds.add(v)
        v_nows = v_changeds
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, _ in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return dist[n - 1]
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return dist[n - 1]
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if v == n - 1:
                return 'inf'
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    edges = []  # ベルマンフォードするなら頂点よりも辺が主役なので
    repn = [[] for _ in range(N)]
    reverse_repn = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        edges.append((a, b, c))
        repn[a].append(b)
        reverse_repn[b].append(a)
    """
    辺の重みを正負逆転させることで単一始点最短経路問題を解けば良い。
    ベルマンフォードで負閉路を検出したら"inf"を返す。
    ABC137Eを参考にする。
    これも負閉路が1~(N-1)のパス上にあることの確認が必要ですね。。。
    """
    reachable_from_1 = [0] * N
    reachable_from_N = [0] * N
    ok = [0] * N

    def dfs(v):
        if reachable_from_1[v]: return
        reachable_from_1[v] = 1
        for u in repn[v]: dfs(u)

    def reverse_dfs(v):
        if reachable_from_N[v]: return
        reachable_from_N[v] = 1
        for u in reverse_repn[v]: reverse_dfs(u)

    dfs(0)
    reverse_dfs(N - 1)
    for i in range(N):
        if reachable_from_1[i] and reachable_from_N[i]: ok[i] = 1

    # ベルマンフォード
    d = [10**18] * N
    d[0] = 0
    step = 0
    update = True
    while update:
        update = False
        for a, b, c in edges:
            if not ok[a]: continue
            if not ok[b]: continue
            new_cost = d[a] - c
            if new_cost < d[b]:
                update = True
                d[b] = new_cost
        step += 1
        if step > N:
            print("inf")
            return
    print(-d[N - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0
    neg = [False] * v

    for i in range(v-1):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
    
    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                neg[q] = True
            if neg[p]:
                neg[q] = True

    if neg[v-1]:
        return False
    else:
        return -dist[v-1]


v, e = map(int, input().split())

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

res = bellman_ford(0)

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

Submission status: Accepted

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0
    neg = [False] * v

    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
    
    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                neg[q] = True
            if neg[p]:
                neg[q] = True

    if neg[v-1]:
        return False
    else:
        return -dist[v-1]


v, e = map(int, input().split())

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

res = bellman_ford(0)

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

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)-1):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    pathnode = n
    while pathnode != start_vertex:
        for neighbor in G[pathnode]:
            if distances[neighbor] < distances[pathnode] + G[pathnode][neighbor]:
                print('inf' , flush=True)
                return -1,-1
        pathnode = parents[pathnode]
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * m
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(m):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    c[i] *= -1
for loop in range(n - 1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[n - 1]

neg = [False] * n
for loop in range(n):
    for i in range(m):
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            neg[b[i]] = True
        if neg[a[i]]:
            neg[b[i]] = True
if neg[n - 1]:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
edges = []
for i in range(M):
    a, b, c = getNM()
    edges.append([a - 1, b - 1, c])

def bellman(edges, num_v):
    dist = [-float('inf') for i in range(num_v)]
    dist[0] = 0

    # 一回目のループ
    for i in range(N - 1):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    # 負閉路検出
    nega = [0] * N
    for i in range(N):
        for edge in edges:
            # rootが既に更新されているなら行く際も更新される
            if nega[edge[0]] == 1:
                nega[edge[1]] = 1
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                nega[edge[1]] = 1

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

    return dist

print(bellman(edges, N)[N - 1])

Submission status: Accepted

Solution code:
INF = -float('inf')

def bellmanford(n,e,r):
  costs = [INF]*n
  costs[r] = 0
  for i in range(n):
    for u,v,c in e:
      if costs[u]+c > costs[v] and costs[u]!=INF:
        costs[v] = costs[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return costs[n-1]

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

print(bellmanford(n,edge,0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

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

INF = 10 ** 40
S = [-INF] * N
S[0] = 0

def score(fst, s, C):
    for nx, p in R[fst]:
        if S[nx] >= s + p or S[nx] >= INF:
            continue
        S[nx] = s + p
        if nx in C:
            S[nx] = INF
        C[nx] = C.get(nx, 0) + 1
        score(nx, S[nx], C)
        C[nx] -= 1
        if C[nx] == 0:
            del C[nx]

score(0, 0, {0: 1})

if S[-1] < INF:
    ans = S[-1]
else:
    ans = "inf"

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dp = [-float("INF")]*(N+1)
dp[1] = 0
edges = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
while cnt < N:
    cnt += 1
    for a,b,c in edges:
        dp[b] = max(dp[a]+c,dp[b])
tmp = dp[N]
cnt = 0
while cnt < N:
    cnt += 1
    for a,b,c in edges:
        dp[b] = max(dp[a]+c,dp[b])
if dp[N] > tmp:
    print("inf")
else:
    print(dp[N])

Submission status: Accepted

Solution code:
def Bellmanford(n,edges,r):
    d = [float('inf')]*n
    d[r] = 0
    for i in range(n):
        for u,v,c in edges:
            if d[u] != float('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):
    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:
import sys
rl=sys.stdin.readline

def main():
    n,m=map(int,rl().strip().split())
    eaw=[list(map(int,rl().strip().split())) for _ in range(m)]
    d=dict(((x[0]-1,x[1]-1),-x[2]) for x in eaw)
    inf=10**14
    mdl=[inf]*n
    mdl[0]=0
    def blrelax(dl,k):
        for _ in range(k):
            for e in iter(d):
                if dl[e[0]]+d[e]<dl[e[1]]:
                    dl[e[1]]=dl[e[0]]+d[e]
    blrelax(mdl,n-1)
    a1=mdl[n-1]
    blrelax(mdl,n)
    a2=mdl[n-1]
    if a1>a2:
        print('inf')
    else:
        print(-a1)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
def belman(s,n,w,es):
    d = [-float("inf")] * n #d[i] : s→iの最短距離
    d[s] = 0
    c = 0
    while True:
      update = False
      for p,q,r in es:
        if d[p] != -float("inf") and d[q] < d[p] + r:
          d[q] = d[p] + r
          update = True
          c += 1
        if c > w:
          return 'inf'
      if not update:
        break
    return d[n-1]

def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used

n,w = map(int,input().split())
es = []
l = [[] for i in range(n)]
r = [[] for i in range(n)]

for i in range(w):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    es.append((a,b,c))

use = use_path(n,0,l) & use_path(n,n-1,r)
ess = [(a,b,c) for a,b,c in es if a in use and b in use]
print(belman(0,n,w*2,ess))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
edges = []
for i in range(M):
    a, b, c = getNM()
    edges.append([a - 1, b - 1, c])

def bellman(edges, num_v):
    dist = [-float('inf') for i in range(num_v)]
    dist[0] = 0

    # 一回目のループ
    for i in range(N - 1):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    # 負閉路検出
    nega = [0] * N
    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]
                nega[edge[1]] = 1

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

    return dist

print(bellman(edges, N)[N - 1])

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

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

# N-1→0の辺を追加してから卿連結判定⇒ゴールにたどり着けない閉路を除外
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')