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 sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

A = 10**10

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

dict = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if b not in dict:
        dict[b] = [(a, -c)]
    else:
        dict[b].append((a, -c))

d = [A for i in range(n+1)]
newd = [A for i in range(n+1)]

d[1] = newd[1] = 0

count = 0
while True:
    count += 1
    for i in range(1,n+1):
        if i in dict:
            for e in dict[i]:
                newd[i] = min([d[e[0]] + e[1], newd[i]])

    if count == n-1: dd = newd[n]

    if count >= 2*n:
        if newd[n] == dd:
            print(-dd)
            sys.exit()
        else:
            print("inf")
            sys.exit()

    d = copy.deepcopy(newd)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

A = -10**10

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

dict = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if b not in dict:
        dict[b] = [(a, c)]
    else:
        dict[b].append((a, c))

d = [A for i in range(n+1)]
newd = [A for i in range(n+1)]

d[1] = newd[1] = 0

count = 0
while True:
    count += 1
    for i in range(1,n+1):
        if i in dict:
            for e in dict[i]:
                newd[i] = max([d[e[0]] + e[1], newd[i]])

    if count == n-1: dd = newd[n]

    if count >= 2*n:
        if newd[n] == dd:
            print(dd)
            sys.exit()
        else:
            print("inf")
            sys.exit()

    d = copy.deepcopy(newd)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

A = -10**10

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

dict = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if b not in dict:
        dict[b] = [(a, c)]
    else:
        dict[b].append((a, c))

d = [A for i in range(n+1)]
newd = [A for i in range(n+1)]

d[1] = newd[1] = 0

count = 0
while True:
    count += 1
    for i in range(1,n+1):
        if i in dict:
            for e in dict[i]:
                newd[i] = max([d[e[0]] + e[1], newd[i]])

    if d == newd: break

    if count >= 5*n:
        if d[n] == newd[n]:
            print(d[n])
            sys.exit()
        else:
            print("inf")
            sys.exit()

    d = copy.deepcopy(newd)

print(d[n])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

A = -10**10

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

dict = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if b not in dict:
        dict[b] = [(a, c)]
    else:
        dict[b].append((a, c))

d = [A for i in range(n+1)]
newd = [A for i in range(n+1)]

d[1] = newd[1] = 0

count = 0
while True:
    count += 1
    for i in range(1,n+1):
        if i in dict:
            for e in dict[i]:
                newd[i] = max([d[e[0]] + e[1], newd[i]])

    if d == newd: break

    if count >= 5*n+1:
        if d[n] == newd[n]:
            print("d[n]")
            sys.exit()
        else:
            print("inf")
            sys.exit()

    d = copy.deepcopy(newd)

print(d[n])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy

A = -10**10

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

dict = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if b not in dict:
        dict[b] = [(a, c)]
    else:
        dict[b].append((a, c))

d = [A for i in range(n+1)]
newd = [A for i in range(n+1)]

d[1] = newd[1] = 0

count = 0
while True:
    for i in range(1,n+1):
        if i in dict:
            for e in dict[i]:
                newd[i] = max([d[e[0]] + e[1], newd[i]])

    if d == newd: break
    d = copy.deepcopy(newd)
    count += 1

    if count >= n+1:
        print("inf")
        sys.exit()

print(d[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
grid = [[-float('inf')]*n for _ in range(n)]
total_w = 0
for i in range(m):
    a, b, c = map(int, input().split())
    grid[a-1][b-1] = c
    total_w += c
for i in range(n):
    for j in range(n):
        if i == j:
            grid[i][j] = 0
res = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            grid[i][j] = max(grid[i][j], grid[i][k] + grid[k][j])
res = grid[0][n-1]

print(res if res <= total_w else 'inf')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
grid = [[-float('inf')]*n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    grid[a-1][b-1] = c

for i in range(n):
    for j in range(n):
        if i == j:
            grid[i][j] = 0
res = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            grid[i][j] = max(grid[i][j], grid[i][k] + grid[k][j])
res = grid[0][n-1]
for i in range(n):
        for j in range(n):
            grid[i][j] = max(grid[i][j], grid[i][n - 1] + grid[n - 1][j])
print(res if res == grid[0][n-1] else 'inf')

Submission status: Wrong Answer

Solution code:
def shortest_path(s,n,w,es):
    d = [-float("inf")] * n #d[i] : s→iの最短距離
    d[s] = 0
    c = 0
    while True:
      update = False
      for p,q,r in es: # e: 辺iについて [from,to,cost]
        if d[p] != -float("inf") and d[q] < d[p] + r:
          d[q] = d[p] + r
          update = True
          c += 1
        if c > w:
          return 'inf'
      if not update:
        break

    return d[n-1]

n,w = map(int,input().split())
es = []

for _ in range(w):
  x,y,z = map(int,input().split())
  es.append([x-1,y-1,z])

print(shortest_path(0,n,w*2,es))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    deg=defaultdict(int)
    memo=defaultdict(int)
    cps=defaultdict(int)
    for x in ew:
        ed[x[0]].append(x[1])
        deg[x[0]]+=1
    prev=0
    curr=1
    scores=[0]*(n+2)
    maxscore=-10**14
    stack=[]
    c=1
    while memo[1]<deg[1]:
        if curr==n:
            maxscore=max(scores[c],maxscore)
        if memo[curr]<deg[curr] and cps[curr]==0:
            cps[curr]=c
            c+=1
            stack.append(prev)
            prev=curr
            curr=ed[curr][memo[curr]]
            scores[c]+=scores[c-1]+ew[(prev,curr)]
        else:
            if cps[curr]>0 and scores[c]-scores[cps[curr]]>0:
                maxscore='inf'
                break
            scores[c]=0
            memo[curr]=0
            memo[prev]+=1
            curr=prev
            prev=stack.pop()
            c-=1
            cps[c]=0
        # print(c,cps,scores)
        # print(list(memo.items()),stack)
    # print(deg)
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    deg=defaultdict(int)
    memo=defaultdict(int)
    cps=defaultdict(int)
    for x in ew:
        ed[x[0]].append(x[1])
        deg[x[0]]+=1
    prev=0
    curr=1
    scores=[0]*(n+2)
    maxscore=-10**14
    stack=[]
    c=1
    while memo[1]<deg[1]:
        if curr==n:
            maxscore=max(scores[c],maxscore)
        if memo[curr]<deg[curr] and cps[curr]==0:
            cps[curr]=c
            c+=1
            stack.append(prev)
            prev=curr
            curr=ed[curr][memo[curr]]
            scores[c]+=scores[c-1]+ew[(prev,curr)]
        else:
            if cps[curr]>0 and scores[c]-scores[cps[curr]-1]>0:
                maxscore='inf'
                break
            scores[c]=0
            memo[curr]=0
            memo[prev]+=1
            curr=prev
            prev=stack.pop()
            c-=1
            cps[c]=0
        # print(c,cps,scores)
        # print(list(memo.items()),stack)
    # print(deg)
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    deg=defaultdict(int)
    memo=defaultdict(int)
    for x in ew:
        ed[x[0]].append(x[1])
        deg[x[0]]+=1
    prev=0
    curr=1
    score=0
    maxscore=-10**14
    stack=[]
    while memo[1]<deg[1]:
        if len(stack)>n+1:
            maxscore='inf'
            break
        if curr==n:
            maxscore=max(score,maxscore)
        if memo[curr]<deg[curr]:
            stack.append(prev)
            prev=curr
            curr=ed[curr][memo[curr]]
            score+=ew[(prev,curr)]
        else:
            score-=ew[(prev,curr)]
            memo[curr]=0
            memo[prev]+=1
            curr=prev
            prev=stack.pop()
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    for x in ew:
        ed[x[0]].append(x[1])
    prev=0
    curr=1
    score=0
    maxscore=-10**14
    stack=[]
    while ed[1]:
        if len(stack)>n+1:
            maxscore='inf'
            break
        if curr==n:
            maxscore=max(score,maxscore)
        if ed[curr]:
            stack.append(prev)
            prev=curr
            curr=ed[curr][-1]
            score+=ew[(prev,curr)]
        else:
            score-=ew[(prev,curr)]
            ed[prev].pop()
            curr=prev
            prev=stack.pop()
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    for x in ew:
        ed[x[0]].append(x[1])
    prev=0
    curr=1
    score=0
    maxscore=-10**14
    stack=[]
    while ed[1]:
        if len(stack)>n:
            maxscore='inf'
            break
        if curr==n:
            maxscore=max(score,maxscore)
        if ed[curr]:
            stack.append(prev)
            prev=curr
            curr=ed[curr][-1]
            score+=ew[(prev,curr)]
        else:
            score-=ew[(prev,curr)]
            ed[prev].pop()
            curr=prev
            prev=stack.pop()
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import networkx as nx

G = nx.DiGraph()

N, M = map(int, input().split())
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, weight=-c)

cG = G.copy()
cG.add_edge(N, 1)
for c in nx.strongly_connected_components(cG):
    if 1 in c:
        sG = G.subgraph(c)
        break
try:
    print(-nx.bellman_ford_path_length(G, 1, N))
except nx.NetworkXUnbounded:
    print('inf')

Submission status: Wrong Answer

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

N, M = map(int, input().split())
frm, to, length = [], [], []
for _ in range(M):
    a, b, c = map(int, input().split())
    frm.append(a - 1)
    to.append(b - 1)
    length.append(-c)
matr = csr_matrix((length, (frm, to)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')

Submission status: Wrong Answer

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

dist = [float('inf')]*n
dist[0] = 0
has_inf_loop = False
for i in range(n):
    if has_inf_loop: break
    for st, en , score in edges:
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            if i == n-1:
                has_inf_loop = True
                break
if has_inf_loop:
    print('inf')
else:
    print(-dist[n-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford():#ﾌﾍｲﾛ検出
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    inf = float("inf")
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=inf and dist[v]+edge[1] < dist[edge[0]]):#dist[v]!=10000:未到達だったら無視するので
                    dist[edge[0]] = dist[v] + edge[1]

    for i in range(n):
        for edge in g[i]:
            if(dist[i]+edge[1] < dist[edge[0]]):
                print("inf")
                exit()

    print(dist[-1]*-1)
    return False

def main():
    bellman_ford()
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def bellman_ford():#ﾌﾍｲﾛ検出
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    inf = float("inf")
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=inf and dist[v]+edge[1] < dist[edge[0]]):#dist[v]!=10000:未到達だったら無視するので
                    dist[edge[0]] = dist[v] + edge[1]
                    if(i==n-1):#n回目でも更新があったら負のループが存在
                        print("inf")
                        exit()

    print(dist[-1]*-1)
    return False

def main():
    bellman_ford()
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def bellman_ford():#ﾌﾍｲﾛ検出
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,-1*c])
    dist = [float("inf")]*n
    dist[0] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(g[v])):
                edge = g[v][k]
                if(dist[v]!=10000 and dist[v]+edge[1] < dist[edge[0]]):#dist[v]!=10000:未到達だったら無視するので
                    dist[edge[0]] = dist[v] + edge[1]
                    if(i==n-1):#n回目でも更新があったら負のループが存在
                        print("inf")
                        exit()

    print(dist[-1]*-1)
    return False

"""
def dijkstra():
    n,m=map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        a,b,c=map(int, input().split())
        g[a-1].append([b-1,c])
        g[b-1].append([a-1,c])
    dist = [10000]*n
    dist[0] = 0
"""
def main():
    bellman_ford()
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v+1 and update:
            print('inf')
            exit()
        elif not update:
            break
    return d[-1]

inf = 1e50
print(-shortest_path(n, 0, edges, inf))

Submission status: Wrong Answer

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v+1 and update:
            print('inf')
            exit()
        elif not update:
            break
    return d[-1]

inf = 1e30
print(-shortest_path(n, 0, edges, inf))

Submission status: Wrong Answer

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v and update:
            print('inf')
            exit()
        elif not update:
            break
    return d[-1]

inf = 1e30
print(-shortest_path(n, 0, edges, inf))

Submission status: Wrong Answer

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v and update:
            print('inf')
            exit()
        elif not update:
            break
    return d[-1]

inf = 10 ** 15
print(-shortest_path(n, 0, edges, inf))

Submission status: Wrong Answer

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

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v and update:
            return False
        elif not update:
            break
    return d[-1]

inf = 10 ** 15
ans = shortest_path(n, 0, edges, inf)
if ans == False:
    print('inf')
else:
    print(-ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

INF = 10 ** 20
def Bellman_Ford(I):
  N = len(I)
  d = [INF for _ in range(N)] # 各頂点への最小コスト
  d[0] = 0 # 自身への距離は0
  visited = [0 for _ in range(N)]
  for i in range(N):
    #print(visited)
    update = False # 更新有無
    task = deque([(0,0,0)])

    visited[0] = i-1
    while task: 
      #print(task, visited, i, d) 
      a, b, c = task.popleft() 
      #print(d[a], d[b], c)
      if d[b] > d[a] + c:
        d[b] = d[a] + c 
        update = True  
      #print(task, visited, i, b) 
      if visited[b] <= i:
        for x, ct in I[b]:
          task.append((b, x, ct))
        visited[b] += 1
    
    if not update:
        break
    
    if i == N - 1:# 負閉路の検知
      return []
  return d

N, M = map(int,input().split()) # N:頂点数, M:辺の数
I = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int,input().split()) # 始点,終点,コスト
  I[a-1].append((b-1,-c))
  #I.append((b,a,c)) 
#print(I)
d = Bellman_Ford(I)
print(-d[N-1] if d else "inf")

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int,input().split())
INF = 10 ** 20
I = [[] for _ in range(N)]
for i in range(M):
  a, b, c = map(int,input().split())
  a -= 1
  b -= 1
  c *= -1 #反転
  I[a].append((b,c))

cost = [INF for _ in range(N)]
visited = [0 for _ in range(N)]
cost[0] = 0
for l in range(N):
  #print(cost, visited)
  a = 0
  edge_num = 0
  edges = [(0,0,0)]
  while edges:
    a, b, c = edges.pop()
    if cost[a] + c < cost[b]:
      cost[b] = cost[a] + c
      if l == N-1:#負の閉路の検出
        print("inf")
        sys.exit()
    
      visited[a] += 1
    
    if visited[b] == l:
      for u, v in I[b]:
         edges.append((b,u,v))
        
print(-cost[N-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  prevd = d[:]
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        update = True
  if not update:
    break
else:
  if prevd[N-1] == d[N-1]:
    pass
  else:
    d[N-1] = 1 #negative cycle  
  
print(-d[N-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b,c = IL()
  graph[a-1].append((b-1,-c))
  
s = 0
d = [INF] * N
d[s] = 0
update = True
for _ in range(N):
  update = False
  for v, e in enumerate(graph):
    for t, cost in e:
      if d[v] != INF and d[v] + cost < d[t]:
        d[t] = d[v] + cost
        if t == N-1:
          update = True
  if not update:
    break
else:
  d[N-1] = -INF #negative cycle  
  
print(-d[N-1])

Submission status: Wrong Answer

Solution code:
# longest version bellman ford
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((c, a-1, b-1))


inf = float("inf")
dist = [-inf for i in range(N)]
dist[0] = 0
is_cycle = False

#辺の緩和
for i in range(N):
    for edge in edges:
        new_dist = dist[edge[1]] + edge[0]
        if dist[edge[2]] < new_dist:
            dist[edge[2]] = new_dist
            if i==N-1:
                is_cycle = True

ans = dist[-1] if not is_cycle else 'inf'
print(ans)