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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

# 求めたい経路の外の閉路にはまるとまずい
#graph = csr_matrix((val,(row,col)),(N+1,N+1))
#try:
#  dist = bellman_ford(graph,indices = [1])[0].astype(int)
#  answer = -dist[N]
#except:
#  answer = 'inf'

from scipy.sparse.csgraph import connected_components
row += (N,)
col += (1,)
val += (1,)

graph = csr_matrix((val,(row,col)),(N+1,N+1))
_,labels = connected_components(graph,connection = 'strong')
idx = (labels == labels[1])

graph2 = graph[idx,:][:,idx]


try:
  dist = bellman_ford(graph,indices = [1])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

graph = csr_matrix((val,(row,col)),(N+1,N+1))
try:
  dist = bellman_ford(graph,indices = [1])[0]
  answer = -int(round(dist[N]))
except:
  answer = 'inf'

print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

graph = csr_matrix((val,(row,col)),(N+1,N+1))
try:
  dist = bellman_ford(graph,indices = [1])[0].astype(int)
  answer = -dist[N]
except:
  answer = 'inf'

print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  #辺の緩和
  for i in range(num_v):
    for e in edges:
      if e[0] != inf and dist[e[1]-1] > dist[e[0]-1] + e[2]:
        dist[e[1]-1] = dist[e[0]-1] + e[2]
        if i == num_v-1:dist[e[1]-1] = inf

  return dist

d = BellmanFord(edge,n,1)

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  #辺の緩和
  for i in range(num_v):
    for e in edges:
      if e[0] != inf and dist[e[1]-1] > dist[e[0]-1] + e[2]:
        dist[e[1]-1] = dist[e[0]-1] + e[2]
        if i==num_v-1: return -1
  return dist
d = BellmanFord(edge,n,1)
if d == -1:
    print("inf")
else:
    print(-1*d[n-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  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
d = BellmanFord(edge,n,0)
if d == -1:
    print("inf")
else:
    print(-1*d[n-2])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

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

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  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
d = BellmanFord(edge,n,0)
if d == -1:
    print("inf")
else:
    print(-1*d[n-2])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
route_list = [[0]*N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	route_list[a-1][b-1] = -c

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [float("inf")] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# 未探索ノードのうちで最小のindex番号を返す関数
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = float("inf") # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

if sum(route_list[N-1])!=0:
	print('inf')
else:
	print(-distance[node_num - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque


n, m = map(int, input().split())
tree = [[] for i in range(n)]
path = {}
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tree[tmp1-1].append([tmp2-1, cost])

q = deque()
q.append([-1, 0])
pos_cost = [-10**10]*n
pos_cost[0] = 0
path = {}

def judge(start):
    q2 = deque()
    q2.append(start)
    visited = [False]*n
    visited[start] = True
    while q2:
        pos = q2.popleft()
        for next_pos, cost in tree[pos]:
            if not visited[next_pos]:
                q2.append(next_pos)
                visited[next_pos] = True
    if visited[n-1]:
        print("inf")
        exit()

while q:
    prev_pos, pos = q.popleft()
    if prev_pos*10000 + pos in path:
        judge(pos)
        continue
    path[prev_pos*10000 + pos] = 1
    for next_pos, cost in tree[pos]:
        if pos_cost[pos] + cost > pos_cost[next_pos]:
            pos_cost[next_pos] = pos_cost[pos] + cost
            q.append([pos, next_pos])
print(pos_cost[n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque


n, m = map(int, input().split())
tree = [[] for i in range(n)]
path = {}
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tree[tmp1-1].append([tmp2-1, cost])
    path[(tmp1-1)*10000 + (tmp2-1)] = False
q = deque()
q.append(0)
pos_cost = [-10**10]*n
pos_cost[0] = 0

def judge(start):
    q2 = deque()
    q2.append(start)
    visited = [False]*n
    visited[start] = True
    while q2:
        pos = q2.popleft()
        for next_pos, cost in tree[pos]:
            if not visited[next_pos]:
                q.append(next_pos)
                visited[next_pos] = True
    if visited[n-1]:
        print("inf")
        exit()

while q:
    pos = q.popleft()
    for next_pos, cost in tree[pos]:
        if pos_cost[pos] + cost > pos_cost[next_pos]:
            if path[pos*10000 + next_pos]:
                judge(pos)
            else:
                pos_cost[next_pos] = pos_cost[pos] + cost
                q.append(next_pos)
                path[pos*10000 + next_pos] = True
print(pos_cost[n-1])

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)

#graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1
try:
    d1 = bellman_ford(graph, indices = N-1, directed=True, unweighted=False)
    print(-int(d1[0]))
except:
    print("inf")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

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

g.sort()
went = [set()] * (N+1)
score = [-10**18] * (N+1)
score[1] = 0

for a,b,c in g:
    score[b] = max(score[a] + c, score[b])
    if b in went[a]:
        print('inf')
        exit()
    else:
        went[b] = went[a] | {a}

print(score[N])

Submission status: Wrong Answer

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf')] * self.N
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf')] * self.N
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Wrong Answer

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Wrong Answer

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Wrong Answer

Solution code:
import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        0-indexedでないことに注意
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: -float('inf'))
        d[1] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    
    next_v = [[] for v in V]
    for i in range(M):
        next_v[a[i]-1].append((b[i]-1, c[i]))
    
    D = [-inf for v in V]
    D[0] = 0
    
    prev = [None for v in V]

    for i in range(N-1):
        for u in V:
            for v, w in next_v[u]:
                alt = D[u] + w
                if alt > D[v]:
                    D[v] = alt
                    prev[v] = u
    
    for u in V:
        for v, w in next_v[u]:
            alt = D[u] + w
            if alt > D[v]:
                print('inf')
                return

    print(D[N-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
negative=[]
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #負閉路の検出
    global negative
    negative=[False for i in range(num_v)]
    #辺の緩和
    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]
                negative[i]=True
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if negative[-1]:
    print("inf")
else:
    print(-ans[N-1])

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
negative=[]
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #負閉路の検出
    global negative
    negative=[False for i in range(num_v)]
    #辺の緩和
    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]
                negative[edge[1]-1]=True
                if negative[edge[0]-1]:
                    negative[edge[1]-1]=True
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1 or negative[-1]:
    print("inf")
else:
    print(-ans[N-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    
    next_v = [[] for v in V]
    for i in range(M):
        next_v[a[i]-1].append((b[i]-1, c[i]))
    
    D = [-inf for v in V]
    D[0] = 0
    
    prev = [None for v in V]

    Q = [(0, 0)]

    while Q:
        v, score = Q.pop()
        for u, w in next_v[v]:
            temp_score = score + w
            if D[u] < temp_score:
                if prev[u] == v:
                    # positive loop found
                    print('inf')
                    return
                D[u] = temp_score
                prev[u] = v
                Q.append((u, D[u]))
    print(D[N-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Wrong Answer

Solution code:
n, m = map(int,input().split())
edge = []
c = []
ed_list = [[] for _ in range(n)]
for i in range(m):
    t_a, t_b, t_c = map(int,input().split())
    edge.append([t_a - 1,  t_b - 1])
    c.append(-t_c)
    ed_list[t_a - 1].append(t_b - 1)
class Topological_sort():
    def __init__(self,v,e):
        self.v = v
        self.list = e
        self.insert = [0]*v
        self.ed_list = [[] for _ in range(v)]
        self.sort_list = []
        for i,j in e:
            self.insert[j] += 1
            self.ed_list[i].append(j)
    def sort(self):
        self.sort_list = []
        stack = []
        self.insert.sort()
        for i in range(self.v):
            if self.insert[i] == 0:
                stack.append(i)
        while stack:
            v1 = stack.pop()
            self.sort_list.append(v1)
            for v2 in self.ed_list[v1]:
                self.insert[v2] -=1
                if self.insert[v2] == 0:
                    stack.append(v2)
    def size(self):
        return len(self.sort_list)

tp = Topological_sort(n, edge)
tp.sort()

if tp.size() == n:
    INF = float('inf')
    score = [INF for _ in range(n)]
    score[0] = 0
    for i in range(n):
        for u, cost in zip(edge, c):
            if score[u[1]] > score[u[0]] + cost:
                score[u[1]] = score[u[0]] + cost
    print(-score[n - 1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
edge = []
c = []
ed_list = [[] for _ in range(n)]
for i in range(m):
    t_a, t_b, t_c = map(int,input().split())
    edge.append([t_a - 1,  t_b - 1])
    c.append(-t_c)
    ed_list[t_a - 1].append(t_b - 1)
class Topological_sort():
    def __init__(self,v,e):
        self.v = v
        self.list = e
        self.insert = [0]*v
        self.ed_list = [[] for _ in range(v)]
        self.sort_list = []
        for i,j in e:
            self.insert[j] += 1
            self.ed_list[i].append(j)
    def sort(self):
        self.sort_list = []
        stack = []
        self.insert.sort()
        for i in range(self.v):
            if self.insert[i] == 0:
                stack.append(i)
        while stack:
            v1 = stack.pop()
            self.sort_list.append(v1)
            for v2 in self.ed_list[v1]:
                self.insert[v2] -=1
                if self.insert[v2] == 0:
                    stack.append(v2)
    def size(self):
        return len(self.sort_list)

tp = Topological_sort(n, edge)
tp.sort()

if tp.size() <= n:
    INF = float('inf')
    score = [INF for _ in range(n)]
    score[0] = 0
    for i in range(n):
        for u, cost in zip(edge, c):
            if score[u[1]] > score[u[0]] + cost:
                score[u[1]] = score[u[0]] + cost
    print(-score[n - 1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
edge = []
c = []
ed_list = [[] for _ in range(n)]
for i in range(m):
    t_a, t_b, t_c = map(int,input().split())
    edge.append([t_a - 1,  t_b - 1])
    c.append(t_c)
    ed_list[t_a - 1].append(t_b - 1)
class Topological_sort():
    def __init__(self,v,e):
        self.v = v
        self.list = e
        self.insert = [0]*v
        self.ed_list = [[] for _ in range(v)]
        self.sort_list = []
        for i,j in e:
            self.insert[j] += 1
            self.ed_list[i].append(j)
    def sort(self):
        self.sort_list = []
        stack = []
        self.insert.sort()
        for i in range(self.v):
            if self.insert[i] == 0:
                stack.append(i)
        while stack:
            v1 = stack.pop()
            self.sort_list.append(v1)
            for v2 in self.ed_list[v1]:
                self.insert[v2] -=1
                if self.insert[v2] == 0:
                    stack.append(v2)
    def size(self):
        return len(self.sort_list)

tp = Topological_sort(n, edge)
tp.sort()

if tp.size() == n:
    INF = float('inf')
    score = [-INF for _ in range(n)]
    score[0] = 0
    for i in range(n):
        for u, cost in zip(edge, c):
            if score[u[1]] < score[u[0]] + cost:
                score[u[1]] = score[u[0]] + cost
    print(score[n - 1])
else:
    print('inf')

Submission status: Wrong Answer

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

def loop_judge(ed_list):
    stack = [0]
    post = set()
    while stack:
        t = stack.pop()
        post.add(t)
        print(t)
        for i in ed_list[t]:
            stack.append(i)
            if i in post:
                return True
    return False
if loop_judge(ed_list):
    print('inf')
else:
    INF = float('inf')
    score = [-INF for i in range(n)]
    score[0] = 0
    for i in range(m):
        for u,v,cost in zip(a,b,c):
            if score[v] < score[u] + cost:
                score[v] = score[u] + cost
    print(score[n-1])

Submission status: Wrong Answer

Solution code:
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())
 
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
#print(d)

def BELLMANFORD(point,d):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1

    return cost,negative

x,y=(BELLMANFORD(1,d))
#print(x,y)
if y[n-1]==1:
    print("inf")
else:
    print(x[n])

Submission status: Wrong Answer

Solution code:
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())
 
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
#print(d)

def BELLMANFORD(point,d):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now

    negative=[0]*n                                        #不閉路の長さは最大n-1であるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1

    return cost,negative

x,y=(BELLMANFORD(1,d))
#print(x,y)

if any(y)==1:
    print("inf")
else:
    print(x[n])