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
INF=float('inf')
def Bellmanford(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[v]>d[u]+c:
        d[v]=d[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return (-1)*d[n-1]
n,m=map(int,input().split())
edges=[0]*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:
def bellmanford(s, n, es):
    # 負の経路の検出
    # n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    neg = [False]*n
    d[s] = 0

    for i in range(n):
        for p, q, r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    neg[q] = True
    return d, neg


n, w = map(int, input().split())  # n:頂点数　w:辺の数
es = []

for _ in range(w):
    x, y, z = map(int, input().split())
    es.append([x-1, y-1, -z])

d, neg = bellmanford(0, n, es)
if neg[-1]:
    print("inf")
else:
    print(-d[-1])

Submission status: Accepted

Solution code:
#ABC061 D Score Attack
#ベルマンフォード法を使う時は、グラフが連結でない場合に注意する。
from collections import deque

def bfs(s, graph):
    visited = [False]*N
    visited[s] = True
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in graph[v]:
            if not visited[nv]:
                visited[nv] = True
                q.append(nv)
    
    return visited

def bellmanford():
    dist = [10**18]*N
    dist[0] = 0
    
    for i in range(N):
        for s, t, c in edges:
            if not visited1[s] or not visited2[t]:
                continue
            
            if dist[t]>dist[s]+c:
                dist[t] = dist[s]+c
                
                if i==N-1:
                    print('inf')
                    exit()

    return dist[-1]

N, M = map(int, input().split())
edges = []
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]

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

visited1 = bfs(0, G)
visited2 = bfs(N-1, rG)

print(-bellmanford())

Submission status: Accepted

Solution code:
import sys
INF=float('inf')
def Bellmanford(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 (-1)*d[n-1]

N,M=map(int, sys.stdin.readline().split())
Edges=[0]*M

for i in range(M):
  a,b,c=map(int, sys.stdin.readline().split())
  Edges[i]=(a-1,b-1,-c)
    
ans=Bellmanford(N,Edges,0)
print(ans)

Submission status: Accepted

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

def readlines(n):
    for _ in range(n):
        a, b, c = map(int, input().split())
        yield a, b, c

def main():
    n, m = map(int, input().split())
    edges = [(a-1, b-1, -c) for a, b, c in readlines(m)]
    costs = bellman_ford(0, edges, n)

    if costs == -1:
        print("inf")
    else:
        print(-costs[-1])

def bellman_ford(start, edges, n):
    inf = float("inf")
    costs = [inf] * n
    costs[start] = 0
    for i in range(n):
        for u, v, weight in edges:
            if costs[u] + weight < costs[v]:
                costs[v] = costs[u] + weight
                if i == n - 1 and v == n - 1:
                    return -1

    return costs

main()

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0

  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==num_v-1: return -1

  return dist

N,M=map(int,input().split())
edges=[]
test=Dijkstra(N)
for i in range(0,M):
    a,b,c=map(int,input().split())
    edges.append([a,b,-c])
    test.add(b-1,a-1,1)

use=set([N-1])
for i in range(0,N-1):
    if test.shortest_path(N-1)[i]!=10**15:
        use.add(i)

useedges=[]
for i in range(0,M):
    a,b,c=edges[i]
    if a-1 in use and b-1 in use:
        useedges.append(edges[i])

ans=BellmanFord(useedges,N,1)
if ans==-1:
    print('inf')
else:
    print(-ans[N-1])

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = dict()

    def add_edge(self, _from, _to, _cost):
        self.edge[(_from, _to)] = _cost

    def fill_cost(self, check=False):
        negative_loops = set()
        for i in range(self.n):
            for (_from, _to), _cost in self.edge.items():
                if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                    self.cost[_to] = self.cost[_from] + _cost
                    if check:
                        negative_loops.add(_to)
        return negative_loops


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)
bf.fill_cost()
negative_loops = bf.fill_cost(check=True)
# print(negative_loops, bf.cost)
if N - 1 in negative_loops:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
std = []
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  std += [[a, b, -c]]

def bellman_ford(s):
  # std = [[s0, t0, d0], [s1, t1, d1], ... , [sm, tm, dm]]
  # (si, ti, di): si, ti間に重さdiの辺がある
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in std:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist != -1:
  print(-dist[n-1])
else:
  print('inf')

Submission status: Accepted

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and v == V-1:
                        return -1
        return dist
    

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    if dist == -1:
        print('inf')
    else:
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
abc = []
for _ in range(m):
    a, b, c = [int(i) for i in input().split()]
    abc.append([a - 1, b - 1, c])

dist = [-10 ** 18] * n
dist[0] = 0

def update():
    global dist
    for a, b, c in abc:
        if dist[a] + c > dist[b]:
            dist[b] = dist[a] + c

for _ in range(n):
    update()
a = dist[-1]
for _ in range(n):
    update()
b = dist[-1]
if a != b:
    print("inf")
else:
    print(a)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = []
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        c *= -1
        graph.append([a, b, c])
    
    def bellman_ford(s):
        dist_ls = [10 ** 15] * N
        dist_ls[s] = 0
        for i in range(N):
            for u, v, w in graph:
                if dist_ls[u] + w < dist_ls[v]:
                    dist_ls[v] = dist_ls[u] + w
                    if i == N - 1 and v == N - 1:
                        return -1
        return dist_ls
    
    dist = bellman_ford(0)
    if dist == -1:
        print('inf')
    else:
        print(-dist[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = []
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        c *= -1
        graph.append([a, b, c])
    
    def bellman_ford(s):
        dist_ls = [10 ** 15] * N
        dist_ls[s] = 0
        for i in range(N):
            for s, t, w in graph:
                if dist_ls[s] + w < dist_ls[t]:
                    dist_ls[t] = dist_ls[s] + w
                    if i == N - 1 and t == N - 1:
                        return -1
        return dist_ls
    
    dist = bellman_ford(0)
    if dist == -1:
        print('inf')
    else:
        print(-1 * dist[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

costs = [-(10**20)]*N
costs[0] = 0

epoch = 0
update_number = 1
L = 0

while update_number > 0 and epoch < 2*(N-1):
    update_number = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            update_number += 1
    epoch += 1
    if epoch == N-1:
        L = costs[N-1]

if epoch == 2*(N-1) and L != costs[N-1]:
    print('inf')
else:
    print(costs[N-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(2*n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
            if b == n - 1 and z >= n - 1:
                print('inf')
                exit()
print(-dis[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:

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

def bellman_ford(s):
  # std = [[s0, t0, d0], [s1, t1, d1], ... , [sm, tm, dm]]
  # (si, ti, di): si, ti間に重さdiの辺がある
  dist = [float('inf')]*n 
  dist[s] = 0
  for u in range(n):
    for s, t, d in abc:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d
        if u == n-1 and t == n-1:
          return -1
  return dist

dist = bellman_ford(0)
if dist == -1:
  print('inf')
else:
  print(-1*dist[n-1])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
link = []
for i in range(m):
    tmp = list(map(int,input().split()))
    link.append([tmp[0]-1,tmp[1]-1,-tmp[2]])

def bell(edges, start,num_v):
    cost = [float('inf')] * num_v
    cost[start] = 0
    for _ in range(num_v):
        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

ans1,d = bell(link,0,n)

if ans1 == -1:
    inf_flag = [False]*n
    for i in range(n):
        for f, t, c in link:
            if d[f] == float("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[-1])

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    
    def BellmanFord(edges,V,source):
        INF = float("inf")
        dist = [INF for _ in range(N)]
        dist[source] = 0
        
        for i in range(V):
            for now,fol,d in edges:
                if dist[now] != INF and dist[fol] > dist[now]+d:
                    dist[fol] = dist[now]+d
                    if i == V-1 and fol == N-1:
                        return "inf"
        return -1*dist[-1]
        
    edge = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        edge.append((a-1,b-1,-c))
    
    print(BellmanFord(edge,N,0))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = sorted([list(map(int,input().split())) for _ in range(m)])
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] - edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] - edge[2]
        if i==num_v-1 and edge[0] == num_v-1: 
          return -1
  return dist
if BellmanFord(g,n,1) == -1:
  print("inf")
else:
  print(-BellmanFord(g,n,1)[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = sorted([list(map(int,input().split())) for _ in range(m)])
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] - edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] - edge[2]
        if i==num_v-1 and edge[0] == num_v-1: return -1
  
  return dist
if BellmanFord(g,n,1) == -1:
  print("inf")
else:
  print(-BellmanFord(g,n,1)[-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    # adj = [[], [(to, cost), (to, cost), ...], [(to, cost), (to, cost), ...], ...]
    def BellmanFord(adj, start):
        N = len(adj) - 1
        inf = 10**13
        dist = [inf] * (N + 1)
        dist[start] = 0
        neg_loop_flg = 0
        for i in range(N):
            updated = 0
            for fr in range(1, N + 1):
                if dist[fr] == inf:
                    continue
                for to, cost in adj[fr]:
                    if dist[fr] + cost < dist[to]:
                        dist[to] = dist[fr] + cost
                        updated = 1
            if not updated:
                break
            if i == N - 1:
                if updated:
                    neg_loop_flg = 1

        return dist, neg_loop_flg

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

    adj_new = [[] for _ in range(N+1)]
    que = deque()
    que.append(N)
    seen = [0] * (N+1)
    seen[N] = 1
    while que:
        v = que.pop()
        for u, cost in adj[v]:
            if not seen[u]:
                seen[u] = 1
                que.append(u)
            adj_new[u].append((v, cost))

    dist, flg = BellmanFord(adj_new, 1)
    if flg:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    d = [inf for _ in range(N)]
    d[0] = 0
    edges = []
    for _ in range(M):
        a, b, c = LI_()
        c += 1
        edges.append((a, b, -c))
    for _ in range(N-1):
        for edge in edges:
            fr, to, cost = edge
            if d[to] > d[fr] + cost:
                d[to] = d[fr] + cost
    neg = [False for _ in range(N)]
    for _ in range(N):
        for edge in edges:
            fr, to, cost = edge
            if neg[fr] == True:
                neg[to] = True
            if d[to] > d[fr] + cost:
                neg[to] = True
    if neg[N-1]:
        print('inf')
    else:
        print(-d[N-1])

main()

Submission status: Accepted

Solution code:
n , m = map(int,input().split())
ainf = -334334334334334334334334
es = []

def bf():
    d = [ainf] * n
    d[0] = 0
    i = 0 
    sa = 0
    ta = 0
    
    for i in range(n+1):
        for p,q,r in es:
            if d[p] != ainf and d[q] < d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    sa = d[n-1]
                if i == n:
                    ta = d[n-1]
                
    return sa,ta,d[n-1]

for _ in range(m):
    x , y , z = map(int,input().split())
    es.append([x-1,y-1,z])
    
s,t,u = bf()

if s == t:
    print(u)
else:
    print("inf")

Submission status: Accepted

Solution code:
def Bellman_Ford(G, start, goal):
    V = len(G)
    INF = float('inf')
    negative = [False] * V
    dist = [INF] * V
    dist[start] = 0
    for i in range(V-1):
        UnUpdate = True
        for v, e in enumerate(G):
            for t, cost in e:
                if dist[v] != INF and dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    UnUpdate = False
        if UnUpdate:
            break

    if not UnUpdate:
        for i in range(V):
            UnUpdate = True
            for v, e in enumerate(G):
                for t, cost in e:
                    if dist[v] != INF and dist[v] + cost < dist[t]:
                        dist[t] = dist[v] + cost
                        negative[t] = True
                        for tt, cct in G[t]:
                            negative[tt] = True
                        UnUpdate = False

            if UnUpdate or negative[goal]:
                break
    if negative[goal]:
        return "inf"
    else:
        return 0-dist[goal]


V, E = map(int, input().split())
G = [[] for i in range(V)]
for i in range(E):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, 0-c))
ans = Bellman_Ford(G,0,V-1)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	# loop 0 - (n-1) : bellman ford
	# loop n - (2n-1): check g can be updated
	dist = [float("inf")] * n
	dist[s] = 0
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					dist[b] = -float("inf")

	if dist[g] == -float("inf"):
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
def bellman_ford(n, edges, s):
  min_dist = [INF] * n

  min_dist[s] = 0

  for i in range(n):
    for (start, end, cost) in edges:
      if min_dist[start] != INF and min_dist[start] + cost < min_dist[end]:
        min_dist[end] = min_dist[start] + cost
        if i == n-1 and end == n-1:
          return -INF
  
  return min_dist

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

edges = []

for i in range(M):
  edge = list(map(int, input().split()))
  edge[0] -= 1
  edge[1] -= 1
  edge[2] = -edge[2]
  edges.append(edge)
min_dist = bellman_ford(N, edges, 0)

if min_dist == -INF:
  print('inf')
else:
  print(-min_dist[-1])

Submission status: Accepted

Solution code:
INF = float('inf')


def Bellmanford(node, edges, source):
    d = [INF] * node  # ある頂点までのコストを保存するリスト
    d[source] = 0

    for i in range(node):
        for start, goal, cost in edges:
            # 辺の始まりの頂点までのコストが INF でなく
            # 辺の向かう先の頂点のコストが、より軽くなる場合に、
            # リストを更新する
            if d[start] != INF and d[start] + cost < d[goal]:
                d[goal] = d[start] + cost
                if i == node-1 and goal == node-1:
                    return 'inf'
    return -d[node-1]


N, M = map(int, input().split())
abc = [map(int, input().split()) for _ in range(M)]
Edges = [None] * M

for i in range(M):
    ai, bi, ci = abc[i]
    Edges[i] = (ai-1, bi-1, -ci)


ans = Bellmanford(N, Edges, 0)
print(ans)

Submission status: Accepted

Solution code:
import sys
INF=float('inf')
def Bellmanford(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 (-1)*d[n-1]
n,m=map(int,input().split())
edges=[0]*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:
n,m = map(int,input().split( ))

E = [[] for _ in range(n+1)]
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append((bi,-ci))
#「nまでの経路で」負閉路が要る
#https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * n
dist[0] = 0
update = 1
for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

ans = dist[n-1]


for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
if ans > dist[n-1]:
    print("inf")
else:
    print(-ans)###-

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
inf = 10 ** 18

N, M = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]

negative = [False] * (N + 1)
cost = [inf] * (N + 1)
cost[1] = 0

for loop in range(N):
    update = False
    for a, b, c in ABC:
        if cost[b] > cost[a] - c:
            cost[b] = cost[a] - c
            if loop == N - 1:
                negative[b] = True

ans = -cost[N]
if negative[N]:
    ans = "inf"
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    inf = float("inf")
    sc = [-inf] * N
    sc[0] = 0
    ans = 0
    for i in range(2 * N):
        for ai, bi, ci in zip(a, b, c):
            ai -= 1
            bi -= 1
            sc[bi] = max(sc[bi], sc[ai] + ci)
        if i == N - 1:
            ans = sc[N - 1]
    if ans < sc[N - 1]:
        print("inf")
        return
    print(sc[N - 1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = float('inf')
# n -> ノード数, edges -> グラフ. Vec<(start, end, cost)>で構成, s -> 始点, e -> 目的地
def bellman_ford(n, edges, s, e):
    
    # 各点への最短距離を保持する配列
    min_dist = [INF] * n

    # start地点への距離は0
    min_dist[s] = 0

    for i in range(n):
        for (start, end, cost) in edges:
            if min_dist[start] != INF and min_dist[start] + cost < min_dist[end]:
                min_dist[end] = min_dist[start] + cost
                # 最短経路の更新がn回目でもまだ行われているようなら閉路あり
                if i == n - 1 and end == n - 1:
                    return INF 
    return min_dist

n, m = map(int, input().split())
# graph -> (start, end, cost) で管理する
graph = []

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

dist = bellman_ford(n, graph, 0, n - 1)
if dist == INF:
    print("inf")
else:
    print(-dist[n - 1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def BellmanFord(edges,num_v,s):
  #グラフの初期化
  inf=float("inf")
  dist=[inf]*num_v
  dist[s]=0
  
  #辺の緩和
  for i in range(num_v-1):
    for edge in edges: #edges[頂点][頂点][重み]
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
  ans=-dist[n-1]
  neg=[False]*num_v
  for i in range(num_v):
    for edge in edges: #edges[頂点][頂点][重み]
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        neg[edge[1]]=True
      if neg[edge[0]]:
        neg[edge[1]]=True
  if neg[n-1]:
    ans='inf'
  return ans
edges=[]
for i in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c*=-1
  edges.append((a,b,c))
print(BellmanFord(edges,n,0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def BellmanFord(edges,num_v,s):
  #グラフの初期化
  inf=float("inf")
  dist=[inf]*num_v
  dist[s]=0
  
  #辺の緩和
  for i in range(num_v):
    for edge in edges: #edges[頂点][頂点][重み]
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1 and edge[1]==num_v-1: return -1
  
  return dist[num_v-1]
edges=[]
for i in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c*=-1
  edges.append((a,b,c))
if BellmanFord(edges,n,0)==-1:
  print('inf')
else:
  print(-BellmanFord(edges,n,0))

Submission status: Accepted

Solution code:
import sys
INF=float('inf')
def Bellmanford(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 (-1)*d[n-1]

N,M=map(int, sys.stdin.readline().split())
Edges=[0]*M

for i in range(M):
  a,b,c=map(int, sys.stdin.readline().split())
  Edges[i]=(a-1,b-1,-c)
    
ans=Bellmanford(N,Edges,0)
print(ans)