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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense, NegativeCycleError
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1 and c != np.inf:
			g2[i][new[j]] = c

try:
	graph = csgraph_from_dense(g2, null_value=np.inf)
	dist = bellman_ford(graph)
	ans = -int(dist[0][l-1])
	print(ans)

except NegativeCycleError:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1 and c != np.inf:
			g2[i][new[j]] = c

try:
	graph = csgraph_from_dense(g2, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[l-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1

	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c

	return passed


connected = dfs(0)
connected_nodes = [i for i, e in enumerate(connected) if e]
new = [-1] * n
for i, e in enumerate(connected_nodes):
	new[e] = i
l = len(connected_nodes)

g2 = [[np.inf] * l for _ in range(l)]
for i, e in enumerate(connected_nodes):
	for j, c in enumerate(g[e]):
		if new[j] != -1:
			g2[i][new[j]] = c

try:
	graph = csgraph_from_dense(g2, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[l-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1
	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c


dfs(0)

try:
	graph = csgraph_from_dense(g, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford, csgraph_from_dense
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1
	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c


dfs(0)

try:
	graph = csgraph_from_dense(g, null_value=np.inf)
	dist = bellman_ford(graph, indices=0)
	ans = -int(dist[n-1])
	print(dist)
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
import numpy as np

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[np.inf] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	passed = [0] * n
	passed[s] = 1
	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if passed[v] == 0:
				passed[v] = 1
				stack.append(v)
			g[u][v] = c


dfs(0)

try:
	dist = bellman_ford(csr_matrix(g), indices=0)
	ans = -int(dist[n-1])
	print(dist)
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

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

adj = [[] for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	adj[a].append([b, -c])

g = [[0] * n for _ in range(n)]


def dfs(s):
	stack = [s]
	can_go = [0] * n
	can_go[s] = 1
	while stack:
		u = stack.pop()
		for v, c in adj[u]:
			if can_go[v] == 0:
				can_go[v] = 1
				stack.append(v)
			g[u][v] = c


dfs(0)

try:
	dist = bellman_ford(csr_matrix(g), indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
import numpy as np

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

g = [[0] * n for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	g[a][b] = -c

try:
	dist = bellman_ford(csr_matrix(g, dtype=np.int64), indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

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

g = [[0] * n for _ in range(n)]
for a, b, c in abc:
	a -= 1
	b -= 1
	g[a][b] = -c

try:
	dist = bellman_ford(csr_matrix(g), indices=0)
	ans = -int(dist[n-1])
	print(ans)

except:
	print("inf")

Submission status: Wrong Answer

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

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

class BellmanFord():
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self,N):
        self.edges = []  # 辺
        self.v_set = set(range(N))  # 頂点の集合
    
    @property
    def E(self):
        """ 辺数 """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)
    
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False

    

def main():
    mod=10**9+7
    N,M=MI()
    
    bf = BellmanFord(N)
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        bf.add(a,b,c*(-1))
        
    if bf.exist_negative_loop():
        print("inf")
    else:
        L=bf.shortest_path(0)
        print(-1*L[-1])

main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import shortest_path, bellman_ford

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

try:
  B = bellman_ford(l, indices=[0])
  ans = int(-B[0][-1])
except:
  ans = "inf"
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
# 頂点数
n=s[0]
# 辺の数
m=s[1]
#距離
dist=[-float('inf')]*n
# へんの情報
E=[]
dist[0]=0
#有効グラフの辺の重み
weight=[[0]*n for i in range(n)]
# 各頂点における重みと子を保存
for i in range(m):
    s = list(map(int, input().split()))
    weight[s[0]-1][s[1]-1]=s[2]
    E.append([s[0]-1,s[1]-1])
# 経路計算
for k in range(n):
    for e in E:
        i=e[0]
        j=e[1]
        #　頂点iにおける最短(今回は最長)経路
        d=dist[i]+weight[i][j]
        if dist[j]<d:
            dist[j]=d

# 閉経路の判定（１なら閉経路なし）
negative = 1
for e in E:
        i = e[0]
        j = e[1]
        #　頂点iにおける最短(今回は最長)経路
        d = dist[i]+weight[i][j]
        if dist[j] < dist[i]+weight[i][j]:
            negative=0

# 閉経路があれば'inf'、なければ最短（最長）経路を表示
if negative==1:
    print(dist[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
# 頂点数
n=s[0]
# 辺の数
m=s[1]
#距離
dist=[-float('inf')]*n
# ある頂点の親
parent={}
# ある頂点の子
chiled=[[] for i in range(n)]
dist[0]=0
#有効グラフの辺
weight=[[0]*n for i in range(n)]
# 各頂点における重みと子を保存
for i in range(m):
    s = list(map(int, input().split()))
    weight[s[0]-1][s[1]-1]=s[2]
    chiled[s[0]-1].append(s[1]-1)
# 経路計算
for i in range(n):
    for j in chiled[i]:
        #　頂点iにおける最短(今回は最長)経路
        d=dist[i]+weight[i][j]
        if dist[j]<d:
            dist[j]=d
            parent[j]=i

# 閉経路の判定（１なら閉経路なし）
negative = 1
for i in range(n):
    for j in chiled[i]:
        if dist[j] < dist[i]+weight[i][j]:
            negative=0

# 閉経路があれば'inf'、なければ最短（最長）経路を表示
if negative==1:
    print(dist[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
# 頂点数
n=s[0]
# 辺の数
m=s[1]
#距離
dist=[-float('inf')]*n
# ある頂点の親
parent={}
# ある頂点の子
chiled=[[] for i in range(n)]
dist[0]=0
#有効グラフの辺
weight=[[0]*n for i in range(n)]
# 各頂点における重みと子を保存
for i in range(m):
    s = list(map(int, input().split()))
    weight[s[0]-1][s[1]-1]=s[2]
    chiled[s[0]-1].append(s[1]-1)
# 経路計算
for i in range(n):
    for j in chiled[i]:
        #　頂点iにおける最短(今回は最長)経路
        d=dist[i]+weight[i][j]
        if dist[j]<d:
            dist[j]=d
            parent[j]=i

# 閉経路の判定（１なら閉経路なし）
negative = 1
for j in chiled[i]:
    if dist[i] < dist[i]+weight[i][j]:
        negative=0
# 閉経路があれば'inf'、なければ最短（最長）経路を表示
if negative==1:
    print(dist[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy
#input()
N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[a].append([b,c])
ac=[]
flag=[0 for i in range(N+1)]
for i in range(1,N+1):
    if not flag[i]:
        stack=[[i,set([i]),0]]
        while stack:
            p,visited,m=stack.pop()
            for np,value in data[p]:
                if not np in visited:
                    tempvisited=copy.copy(visited)
                    tempvisited.add(np)
                    stack.append([np,tempvisited,m+value])
                else:
                    if m+value>0:
                        for nnp in visited:
                            flag[nnp]=1
            if flag[i]:
                break
flaglst=set([i for i in range(len(flag)) if flag[i]==1])
stack=[[1,0,set([1]),1 in flaglst]]
while stack:
    p,m,visited,flag=stack.pop()
    for np,value in data[p]:
        if not flag and np in flaglst:
            flag=1
        if np==N:
            if flag:
                print("inf")
                exit()
            else:
                ac.append(m+value)
        if not np in visited:
            tempvisited=copy.copy(visited)
            tempvisited.add(np)
            stack.append([np,m+value,tempvisited,flag])
print(max(ac))