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:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m=map(int,input().split())
ro,co,w=[],[],[]
for i in range(m):
    a,b,c=map(int,input().split())
    ro.append(a-1)
    co.append(b-1)
    w.append(-c)
g=csr_matrix((w,(ro,co)),shape=(n,n))
try:
    b=bellman_ford(g,indices=0)
    print(int(-b[-1]))
except:
    print('inf')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def BellmanFord(edges,num_v):
        inf=float("inf")
        dist=[inf for i in range(num_v)]
        dist[0]=0
        for i in range(num_v):
                for edge in edges:
                        if  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 inf

        return -1*(dist[num_v-1])

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


print(BellmanFord(g,n))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def BellmanFord(edges,num_v):
        inf=float("inf")
        dist=[inf for i in range(num_v)]
        dist[0]=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 inf

        return -1*(dist[num_v-1])

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


print(BellmanFord(g,n))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def BellmanFord(edges,num_v):
        inf=float("inf")
        dist=[inf for i in range(num_v)]
        dist[0]=0
        for i in range(num_v):
                for edge in edges:
                        if edge[0] != inf   and  dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                                if i==num_v-1 and edge[1]==num_v-1:
                                        return inf

        return -1*(dist[i])

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


print(BellmanFord(g,n))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def BellmanFord(edges,num_v):
        inf=float("inf")
        dist=[inf for i in range(num_v)]
        dist[0]=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 inf

        return -1*(dist[i])

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


print(BellmanFord(g,n))

Submission status: Wrong Answer

Solution code:
print('inf')

Submission status: Wrong Answer

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = 10 ** 17
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Submission status: Wrong Answer

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Submission status: Wrong Answer

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

l_p = [float("inf") if i != 0 else 0 for i in range(n)]
count = 0
updated = True
while updated:
  updated = False
  for edge in list_edge:
    if l_p[edge[0]] != float("Inf") and l_p[edge[1]] > l_p[edge[0]] + edge[2]:
      l_p[edge[1]] = l_p[edge[0]] + edge[2]
      updated = True
      if count == n - 1:
        print("inf")
        exit()
  count += 1
print(-1 * l_p[-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 1300: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 1500: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 1100: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 1100: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(d1[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place]: # 前来た時より点数が悪かったらcontinue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2 and count < 1400: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = 10 ** 15
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place]: # 前来た時より点数が悪かったらcontinue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1100: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2 and count < 1400: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(d1[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = 10 ** 15
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place]: # 前来た時より点数が悪かったらcontinue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1100: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2 and count < 1200: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(d1[N])

Submission status: Wrong Answer

Solution code:
# ABC61 D - Score Attack  preference付

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,n,d):
    cost       = [-float("inf")]*(n+1)
    preference = [None         ]*(n+1)      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for nownode,nextnode,c in d:
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode

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


def main():
    n,m=map(int,input().split())
    
    d=[tuple(map(int,input().split()))for i in [0]*m]
    
    x,y=(BELLMANFORD(1,n,d))
    
    if y[n-1]:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# ABC61 D - Score Attack  preference付

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,n,d):
    cost       = [-float("inf")]*(n+1)
    preference = [None         ]*(n+1)      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for nownode,nextnode,c in d:
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode

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


def main():
    n,m=map(int,input().split())
    
    d=[tuple(map(int,input().split()))for i in [0]*m]
    
    x,y=(BELLMANFORD(1,n,d))
    
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  #infが定数なので論理が逆
                cost[nextnode]=cost[nownode]+c
    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n-1:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n]


def main():
    n,m=map(int,input().split())
    
    d=[]
    for s in range(m):
        a,b,c=map(int,input().split())
        d.append((a,b,-c))
    
    print(BELLMANFORD(1,n,d))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  #infが定数なので論理が逆
                cost[nextnode]=cost[nownode]+c
    
    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n-1:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n-1]


def main():
    n,m=map(int,input().split())
    
    d=[]
    for s in range(m):
        a,b,c=map(int,input().split())
        d.append((a,b,-c))
    
    print(BELLMANFORD(1,n,d))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    print(cost)
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  #infが定数なので論理が逆
                cost[nextnode]=cost[nownode]+c
        print(cost)

    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n-1:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n-1]


def main():
    n,m=map(int,input().split())
    
    d=[]
    for s in range(m):
        a,b,c=map(int,input().split())
        d.append((a,b,-c))
    
    print(BELLMANFORD(1,n,d))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      s -=1
      t -= 1
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1 and t == V:
          return -1 
  return dist

def main():
  N, M = map(int, input().split())
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N, M, 0, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print(-dist[N-1])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      s -=1
      t -= 1
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1:
          return -1 
  return dist

def main():
  N, M = map(int, input().split())
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N, M, 0, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print(-dist[N-1])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1:
          return -1 
  return dist

def main():
  N, M = map(int, input().split())
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N+1, M, 1, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print(-dist[N])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def find_negative_loop(n,w,e):
	d=n*[float("inf")];d[0]=0
	for i in range(n):
		for j in range(w):
			if d[e[j][1]]>d[e[j][0]]+e[j][2]:
				d[e[j][1]]=d[e[j][0]]+e[j][2]
				if i==n-1:return True
	return False
def bellman_ford(s,n,e):
	d=[float("inf")]*n;d[s]=0
	while 1:
		f=True
		for i,j,k in e:
			if d[i]!=float("inf")and d[j]>d[i]+k:d[j]=d[i]+k;f=False
		if f:break
	return d
n,m=map(int,input().split())
e=[]
for _ in range(m):
	a,b,c=map(int,input().split())
	e.append([a-1,b-1,-c])
if find_negative_loop(n,m,e):print("inf");exit()
print(-bellman_ford(0,n,e)[-1])

Submission status: Wrong Answer

Solution code:
INF = float("inf")

N, M, *ABC = map(int, open(0).read().split())

D = [0] + [INF] * (N - 1)
E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

def bellman_ford(N):
    for _ in range(N):
        update = False
        for a, b, c in E:
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                update = True
        if not update:
            return False
    return True

if bellman_ford(2 * N):
    print("inf")
else:
    print(-D[-1])

Submission status: Wrong Answer

Solution code:
INF = float("inf")

N, M, *ABC = map(int, open(0).read().split())

D = [0] + [INF] * (N - 1)
E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

def bellman_ford(N):
    for _ in range(N):
        update = False
        for a, b, c in E:
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                update = True
        if not update:
            return False
    return True

if bellman_ford(N + 1):
    print("inf")
else:
    print(-D[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d = [INF]*n
    d[s] = 0
    for i in range(n-1):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
    return d[n-1]

def find_negative_loop(s,E):
    d = [INF]*n
    d[s] = 0
    for i in range(n):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                if i == n-1:
                    return True
    return False

res = bellmanford(0,E)
if find_negative_loop(0,E):
    print('inf')
else:
    print(res*-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n

def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d[s] = 0
    for i in range(n-1):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
    return d[n-1]

def find_negative_loop(E):
    for i in range(n):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                if i == n-1:
                    return True
    return False

res = bellmanford(0,E)
if find_negative_loop(E):
    print('inf')
else:
    print(res*-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n

def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d[s] = 0
    for i in range(n-1):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                update = True
        if not update:
            break
    return d[n-1]

def find_negative_loop(E):
    for i in range(n):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                if i == n-1:
                    return True
    return False

res = bellmanford(0,E)
if find_negative_loop(E):
    print('inf')
else:
    print(res*-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n

def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d[s] = 0
    for i in range(n):
        if i == n-1:
            return INF
        update = False
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                update = True
        if not update:
            break
    return d[n-1]

res = bellmanford(0,E)
if res == INF:
    print('inf')
else:
    print(res*-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n

def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d[s] = 0
    i = 0
    while True:
        if i == n-1:
            return 'inf'
        update = False
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
                update = True
        if not update:
            break
        i += 1
    return d[n-1]

res = bellmanford(0,E)
if res == 'inf':
    print('inf')
else:
    print(res*-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = -0.001
  try:
    d = np.array(d)
    d = shortest_path(d)
    tmp = (-1*d[0][n-1])
    tmp = str(tmp)
    ans = ""
    for i in range(len(tmp)):
      if tmp[i] != ".":
        ans = ans + tmp[i] 
      else:
        break
    print(ans)

  except:
    print("inf")
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = -0.000001
  try:
    d = np.array(d)
    d = shortest_path(d)
    tmp = (-1*d[0][n-1])
    print(int(-1*d[0][n-1]))

  except:
    print("inf")
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = 0.001
  try:
    d = np.array(d)
    d = shortest_path(d)
    tmp = (-1*d[0][n-1])
    print(int(-1*d[0][n-1]))

  except:
    print("inf")
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = 0.001
  try:
    d = np.array(d)
    d = shortest_path(d)
    print(d)
    tmp = (-1*d[0][n-1])
    print(int(-1*d[0][n-1]))

  except:
    print("inf")
solve()