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
class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n

    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s
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 bellman_ford(a, v, e):
    inf = pow(2, 61) - 1
    dist = [inf] * v
    dist[a] = 0
    for i in range(2 * v):
        f = 0
        for s, t, d in E:
            if not dist[s] == inf and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
                f = 1
        if not f:
            x0 = dist[-1]
            break
        elif f and i == v - 1:
            x0 = dist[-1]
    if x0 == dist[-1]:
        return -dist[-1]
    else:
        return "inf"

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])
ans = bellman_ford(0, n, m)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
abc=[tuple(map(int,input().split())) for _ in range(m)]
Inf=float('inf')
dist=[Inf]*n
dist[0]=0
for i in range(n):
    for a,b,c in abc:
        a,b,c=a-1,b-1,-c
        if dist[b] >dist[a]+c:
            dist[b]=dist[a]+c
            if i==n-1 and b==n-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Accepted

Solution code:
def BellmanFord(start):
    # グラフの初期化 始点を0それ以外をinf
    inf = float("inf")
    dist = [inf] * N
    dist[start] = 0
    
    for i in range(N):
        update = False
        for x, y, z in G:
            if dist[y] > dist[x] + z:
                dist[y] = dist[x] + z
                update = True
                
                # 負の閉路を検出
                if y == N - 1 and i == N - 1:
                    return "inf"

        if update is False:
            break
        
    return -dist[-1]

N, W = map(int, input().split())  # 頂点, 辺
G = []
for _ in range(W):
    x, y, z = map(int, input().split())  # start, end, cost
    x, y, z = x - 1, y - 1, -z
    G.append([x, y, z])
    # G.append([y, x, z]) # 無向グラフのときのみ

d = BellmanFord(0)
print(d)

Submission status: Accepted

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


# https://img.atcoder.jp/abc061/editorial.pdf
# 上のD問題
# BellmanFord
# ベルマンフォード法
# edges:エッジ、有向エッジ[a,b,c]a->bのエッジでコストc
# num_v:頂点の数
# source:始点
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和をnum_v-1回繰り返す。num_v回目に辺の緩和があればそれは閉路。-1を返す。
  for i in range(num_v-1):
    for edge in 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: return -1
  #閉路に含まれる頂点を探す。
  negative=[False]*n
  for i in range(num_v):
    for edge in edges:
      if negative[edge[0]]:negative[edge[1]]=True
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        negative[edge[1]] = True
  return dist[n-1],negative[n-1]
ans,nega=BellmanFord(abc,n,0)
if nega:
  print('inf')
else:
  print(-ans)

Submission status: Accepted

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

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update or cnt == n:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])

Submission status: Accepted

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

class Bellman_Ford:
    def __init__(self, v=None, e=None, lis=None, start=None, end=None, inf=pow(10, 18)):
        self.V = v
        self.E = e
        self.lis = lis
        self.start = start if start else 0
        self.end = end if end else self.V-1
        self.inf = inf
        self.close_minus = False#負の閉路の有無
        self.count = self.V*2-1
        self.negative = [False]*self.V
        self.judge = False

    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    Vは頂点数、Eは辺の数（これは今の所使われない）
    close_minusがTrueなら、負の閉路が存在してしまうので、注意する
    """

    def getlist(self, lis):
        self.lis = lis
    
    def def_start(self, s):
        self.start = s
    
    def def_end(self, e):
        self.end = e

    def def_inf(self, inf):
        self.inf = inf
    
    def def_vertice(self, v):
        self.V = v
    
    def def_edge(self, e):
        self.E = e
    
    def prepare(self):
        self.cost = [self.inf]*self.V # 各頂点への最小コスト
        self.cost[self.start] = 0 # 自身への距離は0

    def search(self):
        for i in range(self.V):
            update = False # 更新が行われたか
            for x, y, z in self.lis:
                if self.cost[y] > self.cost[x] + z:
                    self.cost[y] = self.cost[x] + z
                    update = True
                    if self.count <= self.V:
                        self.negative[y] = True
                    self.count -= 1
                if self.count == self.V:
                    self.judge = True
                if self.count == 0:
                    break
            if not update or not self.count:
                break
            # 負閉路が存在
            if i == self.V - 1:
                self.close_minus = True
                return False
        return True

    def main(self):#これを実行すれば良い
        self.prepare()
        self.search()
    
    def cost_all(self):
        return self.cost

def main():
    n, m = map(int,input().split())
    arrange = [None]*m

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

    bf = Bellman_Ford(v=n, e=m, lis=arrange)
    bf.main()

    for a, b, c in arrange:
        if bf.negative[a]:
            bf.negative[b] = True

    if bf.negative[n-1]:
        print("inf")
    else:
        print(-bf.cost[-1]) 


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    flg = False
    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:
            inf_flg = d[-1]
            flg = True
    if flg:
        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:
                if inf_flg != d[-1]:
                    return "inf"
    return -1 * d[-1]

print(bellman_ford(0))

Submission status: Accepted

Solution code:
INF = -float('inf')
 
def bellmanford(n,e,r):
  costs = [INF]*n
  costs[r] = 0
  for i in range(n):
    for u,v,c in e:
      if costs[u]+c > costs[v] and costs[u]!=INF:
        costs[v] = costs[u]+c
        if i==n-1 and v==n-1:
          return 'inf'
  return costs[n-1]
 
n,m = map(int, input().split())
edge = []
for i in range(m):
  a,b,t = map(int, input().split())
  edge.append((a-1,b-1,t))
 
print(bellmanford(n,edge,0))

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())

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

def dfs(X,s):
    used = {s}
    search = deque([s])
    while search:
        ss = search.pop()
        for sss in X[ss]:
            if sss in used:
                continue
            used.add(sss)
            search.append(sss)
    return used

U = dfs(Adake,0) & dfs(Bdake,N-1)
ABC = [(a,b,c) for (a,b,c) in ABC if a in U and b in U]

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Accepted

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

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        a,b,c = a-1,b-1,-c
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Accepted

Solution code:
import sys
N,M = map(int, input().split())
abc = [[] for _ in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    abc[a-1].append((b-1,c))
    
S = [-float("inf")]*N
S[0] = 0
T = [0]
m = 0
n = 0
j = False
while T:
    t = T.pop(0)
    m += 1
    for tb,tc in abc[t]:
        if S[tb] < S[t]+tc:
            S[tb] = S[t]+tc
            T.append(tb)
    if m > M+1:
        d = abc[tb]
        if N-1 in list(d[i][0] for i in range(len(d))):
            j = True
        n += 1
    if n > M:
        if j:
            print("inf")
            sys.exit()
        else:
            break

print(S[-1])

Submission status: Accepted

Solution code:
#nに行くまでの道で正の閉路があればいくらでも大きくすることができる
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=map(int,input().split())
  es.append((a-1,b-1,c))

def BellmanFord(n,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      #負の経路がある場合
      #さらにこっからn回繰り返してd[n-1]が更新されるかみる
      negative=[False]*n
      for i in range(n):
        for p,q,r in es:
          if d[q]<d[p]+r:
            negative[q]=True
            d[q]=d[p]+r
      if negative[n-1]==True:
        print("inf")
        exit()
      else:
        print(d[n-1])
        exit()
        
  print(d[n-1])
  
  
  
BellmanFord(n,0,es)

Submission status: Accepted

Solution code:
#nに行くまでの道で正の閉路があればいくらでも大きくすることができる
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=map(int,input().split())
  es.append([a-1,b-1,c])

def BellmanFord(n,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      #負の経路がある場合
      #さらにこっからn回繰り返してd[n-1]が更新されるかみる
      negative=[False]*n
      for i in range(n):
        for p,q,r in es:
          if d[q]<d[p]+r:
            negative[q]=True
            d[q]=d[p]+r
      if negative[n-1]==True:
        print("inf")
        exit()
      else:
        print(d[n-1])
        exit()
        
  print(d[n-1])
  
  
  
BellmanFord(n,0,es)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

def bellman_ford(s):
    d = [float('inf')] * N
    d[s] = 0
    for i in range(N):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if i == N - 1 and y == N - 1:  return "inf"
    return -d[N - 1]

N, M = cin()
G = []
bfr = []
for i in range(M):
    s, t, w = cin()
    G.append((s - 1, t - 1, -w))
ans = bellman_ford(0)
print(ans)

Submission status: Accepted

Solution code:
class Edge:

    def __init__(self, origin, to, cost):
        self.origin = origin
        self.to = to
        self.cost = cost

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

edges = [None] * M

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

#コストを最小化するような問題として読み替える

dist = [float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != float("inf") and dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    i += 1

    if not isUpdated:
        break

    if i == N-1:
        break

# print(dist)

#最短経路探索が終了
#負のサイクルを検知する
isUpdated = [False for _ in range(N)]
for i in range(N):
    for e in edges:
        if dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated[e.to] = True


if isUpdated[N-1]:
    print("inf")

else:
    print(-dist[N-1])

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-(10 ** 9 * 2000)] * n

# Bellman-Ford
v[0] = 0
for i in range(n):
    tmp = v[-1]
    for a, b, cost in e:
        if v[a-1] + cost > v[b-1]:
            v[b-1] = v[a-1] + cost
    if tmp != v[-1] and i == n-1: break        
else:
    print(v[n-1])
    exit()

print("inf")

Submission status: Accepted

Solution code:
'''
    [bellman_ford]
'''
def bellman_ford(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**18
    d = [INF]*n
    d[s] = 0
    for i in range(n-1): # max n-1 loops. if update d[] in n-th loop -> negative cycle
        update = False
        for v_from, v_to, cost in g:
            if d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost
                update = True
        if not update:
            return d
    return d
    # else: # if not break until n-th loop -> detect negative cycle
    #     # may do something for negatice cycle
    #     return None


def bellman_ford2(s, n, g, d): # s: start, n: |V|, g; glaph 
    INF = 10**18
    # d = [INF]*n
    # d[s] = 0
    for i in range(n-1): # max n-1 loops. if update d[] in n-th loop -> negative cycle
        update = False
        for v_from, v_to, cost in g:
            if d[v_to] > d[v_from] + cost:
                d[v_to] = -INF
    return d


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

d = bellman_ford(0,n,g)
d2 = bellman_ford2(0,n,g,d[:])

INF = 10**18
if d2[n-1] <= -INF:
    print('inf')
else:
    print(-d[n-1])

Submission status: Accepted

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  negative=[False]*n
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
        if cnt==n-1:
          negative[q]=True
    if cnt==n-1:
      for count in range(n):
        for p,q,r in es:
          if negative[p]:
            negative[q]=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      if negative[n-1]:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
        
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Accepted

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  negative=[False]*n
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
        if cnt==n-1:
          negative[q]=True
    cnt+=1
    if not update:
      break
    if cnt==n:
      if negative[n-1]:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
        
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Accepted

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n+1:
      #正のループがある
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(memo)
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Accepted

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n+1:
      #正のループがある
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Accepted

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n:
      #正のループがある
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split()) 
G=[] ; Y=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])

# den=set([])
# for i  in range(m):
#     if uf.same(0,Y[i][0]): 
#         G.append(Y[i])
#         den.add(Y[i][0]);den.add(Y[i][1])
# now=len(den)

if 1:
    ansdist=[inf for i in range(n)]
    ansdist[0]=0
    for i in range(n-1):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                # if i==2*n+2 : print("inf");exit()

    # return ansdist

ans=-ansdist[-1]
neg=[0]*n
for i in range(n):
    for edge in G:
        a,b,d=edge
        if ansdist[b]>ansdist[a]+d:
            ansdist[b] = ansdist[a]+d
            neg[b]=1
        if neg[a]:neg[b]=1
if neg[-1]:
    print("inf")
else:
    print(ans)

Submission status: Accepted

Solution code:
def bellman_ford(n, s, edges, init_val = float('inf')): 
    d = [init_val] * n
    d[s] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    while updated: #閉路の存在
        updated = False
        for vf, vt, w in edges:
            if d[vt] > d[vf] + w:
                d[vt] = -float('inf')
                updated = True
    return d

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1,b-1,-w))
d = bellman_ford(n, 0, edges)
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Accepted

Solution code:
from collections import deque

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    checker = [-1] * n
    for i in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        i += 1
        while q:
            m = len(q)
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Accepted

Solution code:
class PreallocatedQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.init_val = init_val
        self.count = 0

    def append(self, val):
        if self.count == self.n:
            if self.r == 0:
                self.queue = self.queue + [self.init_val] * self.n
            else:
                self.queue = self.queue[self.l:] + self.queue[:self.r] + [self.init_val] * self.n
                self.l = 0
            self.r = self.n
            self.n *= 2
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.count += 1

    def popleft(self):
        if self.count == 0:
            raise IndexError('popleft from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.count -= 1
        return val

    def pop(self):
        if self.count == 0:
            raise IndexError('pop from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.count -= 1
        return val
    
    def size(self):
        return self.count
    
    def __bool__(self):
        return self.count != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = PreallocatedQueue(edge_n, 0)
    q.append(s)
    checker = [-1] * n
    for i in range(n):
        m = q.count
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        i += 1
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Accepted

Solution code:
def fast_bellman_ford(n, s, graph, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    from_set = {s}
    for _ in range(n):
        next_set = set()
        for vf in from_set:
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    next_set.add(vt)
        from_set = next_set
        if not from_set:
            break
    if from_set: #閉路の存在
        while from_set:
            minus_inf = -float('inf')
            next_set = set()
            for vf in from_set:
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        next_set.add(vt)
            from_set = next_set
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Accepted

Solution code:
def bellman_ford(n, s, edges, init_val): 
    d = [init_val] * n
    d[0] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    if updated: #閉路の存在
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = -float('inf')
    return d

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

edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1, b-1, -w))
d = bellman_ford(n, 0, edges, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Accepted

Solution code:
class BellmanFord:#Union-Find
    def __init__(self, n, init_val = float('inf')):
        self.d = [init_val] * n #根にサイズを負の値で格納する。
        self.init_val = init_val

    def shortest_path(self, s, edges):
        self.d[s] = 0
        for _ in range(n):
            updated = False
            for a, b, w in edges:
                if self.d[a] != self.init_val and self.d[b] > self.d[a] + w:
                    self.d[b] = self.d[a] + w
                    updated = True
            if not updated:
                break
        if updated: #閉路の存在
            for a, b, w in edges:
                if self.d[a] != self.init_val and self.d[b] > self.d[a] + w:
                    self.d[b] = -float('inf')
    
    def get_path_length(self, i):
        return self.d[i]

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

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

bf = BellmanFord(n)
bf.shortest_path(0, edges)
ans = bf.get_path_length(n-1)
print(-ans if ans != -float('inf') else 'inf')