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, c = map(int, input().split())
    a-=1; b-=1
    edges.append((a, b, -c))

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1):
    # n-1回ループすることで、到達できるすべての頂点の更新ができる
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    # n回目以降のループで更新された頂点は負閉路を含む
    # それをn回繰り返して更新された頂点は、負閉路の影響を受けている
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

if negative[n-1]:
    print('inf')
else:
    print(-dist[n-1])

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-=1; b-=1
    edges.append((a, b, -c))

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1): # なぜ？
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

if negative[n-1]:
    print('inf')
else:
    print(-dist[n-1])

Submission status: Accepted

Solution code:
def bellman_ford():#ﾌﾍｲﾛ検出
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    inf = float("inf")
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=inf and dist[v]+edge[1] < dist[edge[0]]):#dist[v]!=10000:未到達だったら無視するので
                    dist[edge[0]] = dist[v] + edge[1]

    ans = dist[n-1]
    neg = [0]*n

    for i in range(n):
        for edge in g[i]:
            if(dist[i]==inf):continue
            if(dist[i]+edge[1] < dist[edge[0]]):
                dist[edge[0]] = dist[i]+edge[1]
                neg[edge[0]]=1
            if(neg[i]):
                neg[edge[0]]=1



    if(not neg[n-1]):
        print(dist[n-1]*-1)
    else:
        print("inf")

    return False


def main():
    bellman_ford()
if __name__ == '__main__':
    main()

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-1, b-1, -c))

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    for i in range(2 * n):
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if i == n:
            memo = d[-1]
    if memo != d[-1]:
        print('inf')
        exit()
    
    return d[-1]

inf = 1e30
print(-shortest_path(n, 0, edges, inf))

Submission status: Accepted

Solution code:
INF = -float("inf")
 
def Bellmanford(n, e):
  dp = [INF] * n
  dp[0] = 0
  for i in range(n):
    for a, b, c in e:
      if dp[a] != INF and dp[a] + c > dp[b]:
        dp[b] = dp[a] + c
        if i == n-1 and b == n-1:
          return "inf"
  return dp[n-1]

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

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

ans = Bellmanford(N, abc) 
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

INF = 10 ** 20
def Bellman_Ford(I):
  N = len(I)
  d = [INF for _ in range(N)] # 各頂点への最小コスト
  d[0] = 0 # 自身への距離は0
  visited = [0 for _ in range(N)]
  for i in range(N-1):
    update = False # 更新有無
    task = deque([(0,0,0)])

    visited[0] = i-1
    while task: 
      a, b, c = task.popleft() 
      if d[b] > d[a] + c:
        d[b] = d[a] + c 
        update = True   
      if visited[b] <= i:
        for x, ct in I[b]:
          task.append((b, x, ct))
        visited[b] += 1
    if not update:
        break
        
  # 負閉路の検知
  visited = [0 for _ in range(N)]
  neg = [0 for _ in range(N)]
  for i in range(N):
    update = False # 更新有無
    task = deque([(0,0,0)])
    visited[0] = i-1
    while task: 
      a, b, c = task.popleft() 
      if d[b] > d[a] + c:
        d[b] = d[a] + c 
        update = True 
        neg[b] = 1
        
      if visited[b] <= i:
        for x, ct in I[b]:
          task.append((b, x, ct))
        visited[b] += 1
        
    if not update:
        break
        
    if neg[N-1] == 1:
      return []
    
  return d

N, M = map(int,input().split()) # N:頂点数, M:辺の数
I = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int,input().split()) # 始点,終点,コスト
  I[a-1].append((b-1,-c))
  #I.append((b,a,c)) 
#print(I)
d = Bellman_Ford(I)
print(-d[N-1] if d else "inf")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
negative = [False] * N
update = True
for _ in range(N):
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        negative[t] = True
        update = True
  if not update:
    break
if negative[N-1]:
  print("inf")
else:
  print(-d[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  prevd = d[:]
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
else:
  if prevd[N-1] == d[N-1]:
    pass
  else:
    d[N-1] = 1 #negative cycle  
if d[N-1] == 1:
  print("inf")
else:
  print(-d[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  prevd = d[:]
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
else:
  if prevd[N-1] == d[N-1]:
    pass
  else:
    d[N-1] = -INF #negative cycle  
  
print(-d[N-1])

Submission status: Accepted

Solution code:
# longest version bellman ford
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))


inf = float("inf")
dist = [-inf for i in range(N)]
dist[0] = 0
is_cycle = False

#辺の緩和
for i in range(N):
    for edge in edges:
        new_dist = dist[edge[0]] + edge[2]
        if dist[edge[1]] < new_dist:
            dist[edge[1]] = new_dist
            if i==N-1 and edge[1] == N-1:
                is_cycle = True

ans = dist[-1] if not is_cycle else 'inf'
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = []

    for _ in range(m):
        a, b, c = map(int, readline().split())
        edge.append((a - 1, b - 1, -c))

    dist = [INF] * n
    dist[0] = 0

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

    loop = [False] * n
    for i in range(n):
        for a, b, c in edge:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                loop[b] = True

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Bellmanford(n, edges):
    dp = [INF] * n
    dp[0] = 0

    for i in range(n):  # たかだかn-1回ループ　n回目でまだ更新できたら負閉路がある
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c > dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return dp[n-1]


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

ans = Bellmanford(N, E)

print(ans)

Submission status: Accepted

Solution code:
INF = float("inf")

def Bellmanford(n, edges):
    dp = [INF] * n
    dp[0] = 0

    for i in range(n):  # たかだかn-1回ループ　n回目でまだ更新できたら負閉路がある
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c < dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return -dp[n-1]


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

ans = Bellmanford(N, E)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = [set() for _ in range(N + 1)]
reve = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].add((v, -c))
  reve[v].append(u)

vis = [0] * (N + 1)
def revdfs(x):
  global vis
  if x == 1: return True
  res = 0
  for y in reve[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= revdfs(y)
  return res
def dfs(x):
  global vis
  if x == N: return True
  res = 0
  for y, _ in e[x]:
    if vis[y]: continue
    vis[y] = 1
    res |= dfs(y)
  return res
banned = [0] * (N + 1)
for x in range(1, N + 1):
  vis = [0] * (N + 1)
  banned[x] |= revdfs(x) ^ 1
  vis = [0] * (N + 1)
  banned[x] |= dfs(x) ^ 1

for x in range(1, N + 1):
  t = list(e[x])
  for y, d in t:
    if banned[x] | banned[y]: e[x].discard((y, d))
#print(banned)
INF = 10**18
dist = [INF] * (N + 1)
dist[1] = 0
update = 1
for _ in range(N + 1):
    update = 0
    for v, x in enumerate(e):
        for t, cost in x:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
  print("inf")
  exit(0)
print(-dist[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
# from, to, cost
edges = [list(map(int, input().split())) for _ in range(m)]

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

for i in range(n):
    for frm, to, cost in edges:
        if score[to] < score[frm] + cost:
            if i == n - 1 and to == n:
                print('inf')
                exit()
            score[to] = score[frm] + cost

print(score[n])

Submission status: Accepted

Solution code:
"""
頂点1から頂点Nまでのルートの途中でサイクルがあれば、無限にスコアを大きくできる。
サイクルがない場合、V-1回でNまでのスコアが求まる。
サイクルがある場合、もう一周回すと、Nまでのスコアが増えているはず。
Nのスコアが増えたらサイクル有、ということ
"""
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0

for _ in range(N-1):
    for a,b,c in edges:
        dp[b] = max(dp[b],dp[a]+c)

tmp1 = dp[N]

for _ in range(N-1):
    for a,b,c in edges:
        dp[b] = max(dp[b],dp[a]+c)

tmp2 = dp[N]
if tmp2 > tmp1:
    print("inf")
else:
    print(tmp1)

Submission status: Accepted

Solution code:
def bellman_ford(s):
    d = [-float("inf")]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    check = [False]*n
    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
        if not update:
            break
        # 負閉路が存在
        if i == n - 1:
          for x, y, z in g:
            if d[y] < d[x] + z:
                d[y] = d[x] + z
                check[x]=True
                check[y]=True
    if check[n-1]:
      return "inf"
    return d[n-1]

n, w = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x-1, y-1, z])
    #g.append([y, x, z]) # 有向グラフでは削除
print(bellman_ford(0))

Submission status: Accepted

Solution code:
# ABC061 D - Score Attack
import sys
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ベルマンフォード法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print(cost[N])

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ワーシャルフロイド法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print(cost[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] >= s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist[g] = hist.get(g, 0) + 1
            helper(g, S[g], hist)
            hist[g] -= 1
            if hist[g] == 0:
                del hist[g]
    helper(0, 0, {0: 1})
    s = S[-1]
    return s if s < INF else 'inf'

print(main())

Submission status: Accepted

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
import sys
buf = sys.stdin.buffer


def main():
    n, m = map(int, buf.readline().split())
    ABC = map(int, buf.read().split())

    edges = []
    routes = [[] for _ in range(n)]
    rev_routes = [[] for _ in range(n)]

    def get_reachable_nodes(start, routes):
        seen = {start}
        todo = []
        for to in routes[start]:
            todo.append(to)
            seen.add(to)

        while todo:
            node = todo.pop()
            for to in routes[node]:
                if to in seen:
                    continue
                todo.append(to)
                seen.add(to)
        return seen

    for node1, node2, value in zip(ABC, ABC, ABC):
        node1, node2 = node1 - 1, node2 - 1
        edges.append([node1, node2, -value])
        routes[node1].append(node2)
        rev_routes[node2].append(node1)

    from_start = get_reachable_nodes(0, routes)
    to_goal = get_reachable_nodes(n-1, rev_routes)
    from_start_to_goal = from_start & to_goal

    values = []
    rows = []
    cols = []

    for row, col, minus_value in edges:
        if {row, col} <= from_start_to_goal:
            values.append(minus_value)
            rows.append(row)
            cols.append(col)

    graph = coo_matrix((values, (rows, cols)), shape=(n, n))
    try:
        bf = bellman_ford(graph, indices=[0])
        print(-int(bf[0][n - 1]))
    except NegativeCycleError:
        print("inf")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[]
a,b,c=0,0,0
for i in range(M):
  a,b,c=map(int,S[i+1].split())
  G.append((a-1,b-1,-c))
INF=10**15
D=[INF]*N
D[0]=0
e=0
for i in range(N-1):
  for j in range(M):
    e=G[j]
    if D[e[0]]!=INF and D[e[1]]>D[e[0]]+e[2]:
      D[e[1]]=D[e[0]]+e[2]
X=D[N-1]
for j in range(M):
  e=G[j]
  if D[e[0]]!=INF and D[e[1]]>D[e[0]]+e[2]:
    D[e[1]]=D[e[0]]+e[2]
if X==D[N-1]:
  print(-X)
else:
  print('inf')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edges = []
for _ in range(M):
    s,t,d = map(int,input().split())
    edges.append((s,t,d))

cost = [-1*float("INF") for _ in range(N+1)]
cost[1] = 0
count = 0
while count < N:
    count += 1
    for s,t,d in edges:
        if cost[s] + d > cost[t]:
            cost[t] = cost[s] + d
ans = cost[N]

negative = [False]*(N+1)
count = 0
while count <= N:
    count += 1
    for s,t,d in edges:
        if cost[s] + d > cost[t]:
            cost[t] = cost[s] + d
            negative[t] = True
for s,t,d in edges:
        if negative[s]:
            negative[t] = True

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

Submission status: Accepted

Solution code:
class Graph():  #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def bellman_ford(self, s, t=None, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        update = True
        for i in range(self.n):
            update = False
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        update = True
            if not update:
                return dist[t] if t is not None else dist
        if t is None:
            return
        negative_cycle = [0 for _ in range(self.n)]
        for i in range(self.n):
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        negative_cycle[adj] = True
        if not negative_cycle[t]:
            return dist[t]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = []

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

g = Graph(N, E)
bf = g.bellman_ford(0, N - 1)

print(-bf if bf is not None else 'inf')