Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



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


Sample output:
7

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

    

def main():
    mod=10**9+7
    N,M=MI()
    edges=[None]*M
    
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        c*=-1
        edges[i]=(a,b,c)
        
    ########################    
    #0から他の頂点へ
    def BellmanFord(N, M, edges):
        inf=10**20
        d = [inf] * N
        d[0] = 0

        for i in range(N-1):
            for (u, v, c) in edges:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c

        #for i in range(N):
        for (u, v, c) in edges:
            if d[u] + c < d[v]:
                if v == N-1:
                    return None#負の閉路
                
                d[v] = d[u] + c
        return d[N-1]
    ########################
        
    ans = BellmanFord(N, M, edges)
    if ans is None:
        print('inf')
    else:
        print(-ans)

main()

Submission status: Accepted

Solution code:
def bellmanFord(edges):
    dist = [float('inf')] * N
    dist[0] = 0
    for _ in range(N-1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    res = -dist[-1]
    neg = [False] * N
    for _ in range(N):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                neg[v] = True
            if neg[u]:
                neg[v] = True
    if neg[-1]:
        res = 'inf'
    return res

N, M = map(int, input().split())
A = [tuple()] * M
for i in range(M):
    a, b, c = map(int, input().split())
    A[i] = (a-1, b-1, -c)
ans = bellmanFord(A)
print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


# 有向グラフ各辺のコストを集めて最大化する問題だが、全部符号を変えれば最短経路問題にできる

from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class BellmanFord(object):

    def __init__(self, v_len, edges, start):
        """
        隣接行列を使っていないので、有向グラフにのみ適用可能。
        ベルマンフォード法によって最短経路を求める。
        ダイクストラと違って負の数も扱えるが、O(|V||E|) なのでダイクストラより遅い。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: 辺のリスト
        :param start: 始点 単一視点最短経路問題として解くので必要
        """
        self._dist = [float('inf') for _ in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for _ in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(edges, start)

    def _solve(self, edges, start):
        self._dist[start] = 0

        cnt = 0
        while True:  # 更新は高々 |V| - 1 回で終わる
            cnt += 1
            updated = False
            for e in edges:
                if self._dist[e.src] + e.cost < self._dist[e.dst]:
                    self._dist[e.dst] = self._dist[e.src] + e.cost
                    self._prev[e.dst] = e.src
                    if cnt >= len(self._dist):
                        self._dist[e.dst] = float('-inf')
                    updated = True
            if not updated:
                break

    def distance(self, goal):
        """
        負の閉路を含む場合は -inf を返す。
        """
        return self._dist[goal]

    def path(self, goal):
        """
        負の閉路を含む場合は計算が終わらない。
        """
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N, M = MI()
edges = list()
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, -1 * c))
bf = BellmanFord(N + 1, edges, 1)
print(-1 * bf.distance(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N
edges = [0] * M
for m in range(M):
    edges[m] = tuple([int(x) for x in input().strip().split()])

for n in range(N):
    updated = False
    for (i, j, c) in edges:
        # print('i={}, j={}'.format(i, j), end='')
        if score[j-1] < score[i-1] + c:
            score[j-1] = score[i-1] + c
            if j == N-1:
                updated = True
        # print(score)
    if not updated:
        break

if updated:
    print('inf')
else:
    print(score[N-1])

Submission status: Accepted

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

minimumScore = [float('inf') for _ in range(N)]
minimumScore[0] = 0
for _ in range(N-1):
    flag = False
    for a, b, c in paths:
        c = -c
        if minimumScore[a-1] == -float('inf'):
            continue
        if minimumScore[a-1] + c < minimumScore[b-1]:
            minimumScore[b-1] = minimumScore[a-1] + c
            flag = True
    if not flag:
        break


negative = [False for i in range(N)]
for _ in range(N):
    for a, b, c in paths:
        c = -c
        if negative[a-1]:
            negative[b-1] = True
        if minimumScore[a-1] == -float('inf'):
            continue
        if minimumScore[a-1] + c < minimumScore[b-1]:
            negative[b-1] = True
            flag = True
if negative[-1]:
    print('inf')
else:
    print(-minimumScore[N-1])
#print(minimumScore[-1])

Submission status: Accepted

Solution code:
#Nは頂点数, Mは辺数(2 <= N <= 1000, 1 <= M <= min(N(N-1, 2000)))
#頂点1から頂点Nに移動して、移動スコアを最大にする
#->移動スコアを正負反転させれば最短経路問題
#->負閉路を考慮してベルマンフォード法を利用
INF = 1 << 50

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

#辺を登録
Sides = []
for i in range (M):
    Side = list(map(int,input().split()))
    Sides.append(Side)
#コストを反転
    Sides[i][2] = Sides[i][2] * (-1)

#各頂点の最短距離を初期化
Vertexes = [INF]*(N+1)
Vertexes[1] = 0

#負閉路のチェック用
negative = [False] * (N+1)

#ベルマンフォード法による最短距離探索
for count in range(N):
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        cost = Sides[i][2]
        if (Vertexes[to_v] > Vertexes[from_v]+cost):
#N回目の更新で更新された場合は負閉路あり
            if(count==N-1):
                negative[to_v] = True
            else:
                Vertexes[to_v] = Vertexes[from_v]+cost

#負閉路が終点までにあるか確認
for count in range(N-1):
    flag = 0
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        if negative[from_v] and negative[to_v] is False:
            negative[to_v] = True
            flag = 1
    if flag ==0:
        break

if negative[N]:
    print('inf')
else:
    print(-Vertexes[N])

Submission status: Accepted

Solution code:
#Nは頂点数, Mは辺数(2 <= N <= 1000, 1 <= M <= min(N(N-1, 2000)))
#頂点1から頂点Nに移動して、移動スコアを最大にする
#->移動スコアを正負反転させれば最短経路問題
#->負閉路を考慮してベルマンフォード法を利用
INF = 1 << 50

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

#辺を登録
Sides = []
for i in range (M):
    Side = list(map(int,input().split()))
    Sides.append(Side)
#コストを反転
    Sides[i][2] = Sides[i][2] * (-1)

#各頂点の最短距離を初期化
Vertexes = [INF]*(N+1)
Vertexes[1] = 0

#負閉路のチェック用
negative = [False] * (N+1)

#ベルマンフォード法による最短距離探索
for count in range(N):
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        cost = Sides[i][2]
        if (Vertexes[to_v] > Vertexes[from_v]+cost):
            if(count==N-1):
                negative[to_v] = True
            else:
                Vertexes[to_v] = Vertexes[from_v]+cost

#負閉路の確認
for count in range(N-1):
    flag = 0
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        if negative[from_v] :
            negative[to_v] = True
            flag = 1
    #if flag ==0:
     #   break

if negative[N]:
    print('inf')
else:
    print(-Vertexes[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [-float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=-float('inf') and dist[b]<dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>2*N:
    flag = True
    break

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
INF = float("inf")
d = [INF]*N
edges = [None]*M
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[i] = (a,b,-c)
d[0] = 0
for cnt in range(N):
    update = False
    for i in range(M):
        a,b,c = edges[i]
        if d[b] > d[a]+c:
            d[b] = d[a]+c
            update = True
            if cnt == N-1 and b == N-1:
                print("inf")
                exit(0)
    if not update:
        break
print(-d[N-1])

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]

idle_max=10**18+1

dist=[idle_max for i in range(N+1)]
dist[1]=0


for loop in range(N-1):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])

value=dist[N]
for loop in range(N):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])
if value!=dist[N]:
    print("inf")
else:
    print(-value)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        # print(d)
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    # print(loop)
    if loop[n-1]:
        return "inf"

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    # print(graph)
    ans = search(graph, n, m)

    print(ans)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
def bell(edges, n):
    count = 0
    dist = [float('inf') for i in range(n)]
    dist[0] = 0

 
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2] and edge[0] != float('inf'):
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if (i == n - 1) & (edge[1] == n - 1):
                    print('inf')
                    exit()
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, -c])
 
res = bell(edges, n)
 
print(-res[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, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])
 
dist = [float('inf')] * N
dist[0] = 0
 
for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()
 
print(-dist[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    loop = False
    for i in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
                    if i==n-1 and u==n-1:
                        loop = True
        if not updated:
            break
    return d,loop


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
abc = [[int(x) for x in input().split()] for _ in range(M)]
Edges = [None]*M
for i in range(M):
    Edges[i] = (abc[i][0]-1, abc[i][1]-1, -abc[i][2])
def bellman_ford(N, edges, s):
    dist = [float("inf")]*(N)
    dist[s] = 0
    for n in range(N):
        for (u,v,c) in edges:
            if dist[u] != float("inf") and dist[v] >  dist[u] + c:
                dist[v] = dist[u] + c
                if n == N-1 and v == N-1:
                    return "inf"
    return -dist[-1]
print(bellman_ford(N, Edges, 0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
vve = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,e in vve:
  graph[a].append((b,-e))
score = [10**15 for i in range(n+1)]
score[1] = 0
for j in range(n+1):
  flg = 0
  for i in range(m):
    v1,v2,e = vve[i]
    e = -e
    if score[v1] != 10**15 and score[v2] > score[v1]+e:
      score[v2] = score[v1]+e
      flg = 1
      if j == n-1:
        p = -score[n]
      if j == n:
        q = -score[n]
  if flg == 0:
    break
if flg == 0:
  print(-score[n])
else:
  if p == q:
    print(p)
  else:
    print("inf")

Submission status: Accepted

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


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

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

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:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None:
                continue
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None or distance[b - 1] is None:
                continue
            if distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c
                if b == n:
                    return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Accepted

Solution code:
def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0
    for _ in range(num):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated:
            break
    else:
        return (-1,cost)
    return (1,cost[goal])

def main():
    N, M = LI()
    v = []
    for _ in range(M):
        x, y, z = map(int, input().split())
        v.append((x - 1, y - 1, -z))
#    print(v)
#    print(bellmanford(N, 0, N-1, v))
    cur, d = bellmanford(N, 0, N - 1, v)
    if cur == -1:
        # Nまでの道の途中に負閉路があるか
        inf_flag = [False] * N
        for _ in range(N):
            for f, t, c in v:
                if d[f] == inf: continue
                if inf_flag[f] == True:
                    inf_flag[t] = True
                # 更新が終わっていない→負閉路
                if d[t] > d[f] + c:
                    d[t] = d[f] + c
                    inf_flag[t] = True
        print("inf" if inf_flag[N - 1] else -d[N - 1])
    else:
        print(-d)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    main()

"""
3 3
1 2 4
2 3 3
1 3 5
"""

Submission status: Accepted

Solution code:

def Bellman_Ford(node_num:int,start:int,goal:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    if Ans[goal] == Pre[goal]:
        return Ans[goal]
    else:
        return float("inf")
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    ans = Bellman_Ford(N,1,N,newABC)
    print(-ans if ans < float("inf") else "inf")
    return


if __name__ == "__main__":
    main()

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

INF = 10**20
V = [INF]*N
V[0] = 0
for _ in range(N):
  for a, b, c in E:
    d = V[a]+c
    if d < V[b]: V[b] = d

R = [False]*N
R[-1] = True
for _ in range(N):
  for a, b, c in E:
    R[a] |= R[b]

for a, b, c in E:
  if V[a]+c<V[b] and R[b]:
    print('inf')
    exit()
    
print(-V[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, M = Scanner.map_int()

    class Edge():
        def __init__(self, a, b, c):
            self.from_ = a
            self.to_ = b
            self.cost_ = c
    edges = [Edge] * M
    for i in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        c = -c
        edges[i] = Edge(a, b, c)
    dist = [INF] * N
    dist[0] = 0
    for loop in range(N-1):
        for i in range(M):
            e = edges[i]
            if dist[e.from_] == INF:
                continue
            if dist[e.to_] > dist[e.from_] + e.cost_:
                dist[e.to_] = dist[e.from_] + e.cost_
    ans = dist[N-1]
    negatives = [False] * N
    for loop in range(N):
        for i in range(M):
            e = edges[i]
            if dist[e.from_] == INF:
                continue
            if dist[e.to_] > dist[e.from_] + e.cost_:
                dist[e.to_] = dist[e.from_] + e.cost_
                negatives[e.to_] = True
            if negatives[e.from_]:
                negatives[e.to_] = True
    if negatives[N-1]:
        print("inf")
    else:
        print(-ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ABC061D - Score Attack
#https://atcoder.jp/contests/abc061/tasks/abc061_d

import sys
 
inf = float('inf')
 
n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))
 
def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)
 
    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf
 
    return -dist[n-1]
 
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

# Bellman-Ford法
# ベルマンフォード法

N, M = map(int, input().split())
#EDGES = [[] for _ in range(N+1)]
EDGES = []

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

INF = 10 ** 18
d = [INF] * (N+1)
d[1] = 0

ans = 0
for k in range(N):
    update = False
    for i in range(M):
        a, b, c = EDGES[i]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            update = True

            if k == N-1 and b == N:
                print('inf')
                exit()

    if not update:
        break

print(-d[N])

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    cost = [-INF] * N
    cost[0] = 0
    for i in range(N-1):
        for a, b, c in ABC:
            cost[b-1] = max(cost[b-1], cost[a-1] + c)
    prev = cost[N-1]
    for a, b, c in ABC:
        cost[b-1] = max(cost[b-1], cost[a-1] + c)    
    print(cost[N-1] if cost[N-1] == prev else "inf")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def shortest_path(s,n,w,es):
#s→iの最短距離
# s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float('inf')] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    while True:
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
            ans1=d[-1]
        update = False
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
            ans2=d[-1]
        return -ans1 if ans1==ans2 else 'inf' 
################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]
for _ in range(w):
 x,y,z = map(int,input().split())
 es.append([x-1,y-1,-z])
print(shortest_path(0,n,w,es))

Submission status: Accepted

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


for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            if node[b] < node[i]+c:
                node[b] = float('inf')
print(node[-1])

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().split()]
A=[]
B=[]
C=[]

for i in range(M):
	a,b,c=[int(x) for x in input().split()]
	A.append(a-1)
	B.append(b-1)
	C.append(-c)
INF=10000000000000
dist=[INF for i in range(N)]

dist[0]=0


for temp in range(N-1):
	for i in range(M):
		if dist[A[i]]!=INF:
			if dist[B[i]]>dist[A[i]]+C[i]:
				dist[B[i]]=dist[A[i]]+C[i]

checker=[0 for i in range(N)]
ans=dist[N-1]

for temp in range(N):
	for i in range(M):
		if dist[A[i]]!=INF:
			if dist[B[i]]>dist[A[i]]+C[i]:
				dist[B[i]]=dist[A[i]]+C[i]
				checker[B[i]]=1
			if checker[A[i]]==1:
				checker[B[i]]=1

if checker[N-1]==1:
	print("inf")
else:
	print(-ans)