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: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = float("inf")

start = []
end = []
weight = []
node_cost = [-INF] * N
for _ in range(M):
    a, b, c = map(int, input().split())
    start.append(a - 1)
    end.append(b - 1)
    weight.append(c)

node_cost[0] = 0
for _ in range(N - 1):
    for i in range(M):
        new_cost = node_cost[start[i]] + weight[i]
        if new_cost > node_cost[end[i]]:
            node_cost[end[i]] = new_cost
ans = node_cost[N-1]
for i in range(M):
    new_cost = node_cost[start[i]] + weight[i]
    if new_cost > node_cost[end[i]]:
        ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
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

def BellmanFord(graph,num_v,source=0):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
#       負閉路があっても、それを通ってスタートからゴールに辿り着けない場合は結果に影響しない事に注意！
#       ゴールに辿り着ける閉路でも、距離が大きなパスと負閉路が繋がっていて、比較的短い距離のパスが並列している場合、ゴールへの距離の収束には時間ががかかる。
#       Eg. A=>B 1, B=>C 10**18, B=>B -1, A=>C 10, の場合A=>Cはいくらでも小さくなるが収束にはO(10**18)かかる
#        if i==num_v-1:
#            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    return neg_flg,dist
N , M = map(int,input().split())
graph = [[] for i in range(N)]
for i in range(M):
  a , b , c = map(int,input().split())
  a -= 1
  b -= 1
  c *= -1
  graph[a].append((b,c))

#print(graph)
n , d = BellmanFord(graph,N,0)  
if n:
  print('inf')
else:
  print(-d[N-1])

Submission status: Wrong Answer

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:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Wrong Answer

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 update is False:
            break

        # 負の閉路を検出
        if i == N - 1:
            return -1
    
    return dist

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)
if d != -1:
    print(-d[N - 1])
else:
    print("inf")

Submission status: Wrong Answer

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 update is False:
            break

        # 負の閉路を検出
        if i == N - 1:
            return -1
    
    return dist

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

d = BellmanFord(0)
if d != -1:
    print(d[N - 1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:

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回で収束する
    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 not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n+1):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n:
                    return True
    return False

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



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
else:
  print(-bellman_ford(N, es,0)[N-1])

Submission status: Wrong Answer

Solution code:

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回で収束する
    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 not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n - 1:
                    return True
    return False

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



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
else:
  print(-bellman_ford(N, es,0)[N-1])

Submission status: Wrong Answer

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.already = [False]*self.V

    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    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 x == self.V - 1 or self.already[x]:
                        self.already[y] = True

            if not update:
                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()

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 i in range(n):
        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: Wrong Answer

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


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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#負の閉路の有無

    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    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 not update:
                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()

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=float('inf')):
        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#負の閉路の有無

    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    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 not update:
                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()

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=float('inf')):
        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.already = [False]*v
        self.infjudge = False
        self.already[0] = True
    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    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.already[y]:
                        self.infjudge = True
                        break
                    self.already[y] = True
                    """
            if not update or self.infjudge:
                break
            # 負閉路が存在
            if i == self.V - 1:
                self.close_minus = True
                return False
        return True

    def main(self):#これを実行すれば良い
        self.prepare()
        return 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)
    judge = bf.main()

    if not judge:
        print("inf")
    else:
        print(-bf.cost[-1]) 


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=float('inf')):
        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.already = [False]*v
        self.infjudge = False
        self.already[0] = True
    """
    リストは各要素が(始点、終点、重み)となる有向辺の集合とする(無向なら両方作る必要あり)
    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.already[y]:
                        self.infjudge = True
                        break
                    self.already[y] = True
            if not update or self.infjudge:
                break
            # 負閉路が存在
            if i == self.V - 1:
                self.close_minus = True
                return False
        return True

    def main(self):#これを実行すれば良い
        self.prepare()
        return 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)
    judge = bf.main()

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=float('inf')):
        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.already = [False]*v
        self.infjudge = 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.already[y]:
                        self.infjudge = True
                        break
                    self.already[y] = True
            if not update or self.infjudge:
                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()

    if bf.infjudge:
        print("inf")
    else:
        print(-bf.cost[-1])    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n, m = map(int,input().split())
    node = [[] for i in range(n)]
    out = [-1]*n
    for i in range(m):
        a, b, c = map(int, input().split())
        node[a-1].append((b-1, c))
        out[b-1] += 1
    
    not_yet = [(0, 0)]
    already = [False]*n
    dist = [0]*n

    already[0] = True
    judge = False
    while not_yet:
        cost, key = heappop(not_yet)
        if out[key] > 0:
            dist[key] = cost
            out[key] -= 1
            continue
        dist[key] = cost
        already[key] = True

        for k, c in node[key]:
            if already[k]:
                if dist[key] + c - dist[k] > 0:
                    judge = True
                    break
            heappush(not_yet, (cost+c, k))

        if judge:
            break

    if judge:
        print("inf")
    else:
        print(dist[-1])
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n, m = map(int,input().split())
    node = [[] for i in range(n)]
    out = [-1]*n
    for i in range(m):
        a, b, c = map(int, input().split())
        node[a-1].append((b-1, c))
        out[b-1] += 1
    
    not_yet = [(0, 0)]
    already = [False]*n
    dist = [0]*n

    already[0] = True
    judge = False
    while not_yet:
        cost, key = heappop(not_yet)
        if out[key] > 0:
            out[key] -= 1
            continue
        dist[key] = cost
        already[key] = True

        for k, c in node[key]:
            if already[k]:
                if dist[key] + c - dist[k] > 0:
                    judge = True
                    break
            heappush(not_yet, (cost+c, k))

        if judge:
            break

    if judge:
        print("inf")
    else:
        print(dist[-1])
    
     
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    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:
            return "inf"
    return -1 * d[-1]

print(bellman_ford(0))

Submission status: Wrong Answer

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[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Wrong Answer

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:
                print('inf')
                exit()
print(-dist[-1])