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:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i > n and v == n - 1:
                print('inf')
                exit()
    i += 1
    if i > n*m:
        print('inf')
        exit()

print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = [set() for _ in range(n+1)]
vs[0].add(0)

for i in range(n):
    while vs[i]:
        cur_v = vs[i].pop()
        for v,c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if v not in vs[i]:
                    vs[i+1].add(v)
if vs[-1]:
    print('inf')
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
    i += 1
    if i > n and cur_v == n-1:
        print('inf')
        exit()
    if i>n+1:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
    i += 1
    if i > n and cur_v == n-1:
        print('inf')
        exit()
    if i>n+1:
        break
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0

for i in range(n):
    for cur_v in range(n):
        for v, c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if i == n-1:
                    print('inf')
                    exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = [0]

for i in range(n):
    new_vs = []
    while vs:
        cur_v = vs.pop()
        for v, c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if v not in vs:
                    new_vs.append(v)
    vs = new_vs

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

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = [[0]] + [[] for _ in range(n+1)]
i = 0

for i in range(n+1):
    while vs[i]:
        cur_v = vs[i].pop()
        for v,c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if v not in vs:
                    vs[i+1].append(v)
        if i == n:
            print('inf')
            exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = [0]
i = 0
while vs:
    cur_v = vs.pop()
    for v,c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            i += 1
            if v not in vs:
                vs.append(v)
    if i > n*m:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = [0]
i = 0
while vs:
    cur_v = vs.pop()
    for v,c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            if v not in vs:
                i += 1
                vs.append(v)
    if i > n:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v,c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
    i += 1
    if i > 2010:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v,c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
    i += 1
    if i > n+1:
        print('inf')
        import sys
        sys.exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v,c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
    i += 1
    if i > n:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
infinite = -10**14
score = [infinite for _ in range(n+1)]
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n+2): 
    rev = 0
    for i in range(1,n+1):
        for (to, sc) in routes[i]:
            if score[to] < score[i] + sc:
                score[to] = score[i] + sc
                rev += 1
    if rev == 0 and r > n:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
infinite = -10**14
score = [infinite for _ in range(n+1)]
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n+2): 
    rev = 0
    for i in range(1,n+1):
        for (to, sc) in routes[i]:
            if score[to] < score[i] + sc:
                score[to] = score[i] + sc
                if to == n:
                    rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
infinite = -10**14
score = [infinite for _ in range(n+1)]
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n+1): 
    rev = 0
    for i in range(1,n+1):
        for (to, sc) in routes[i]:
            if score[i] != infinite and score[to] < score[i] + sc:
                score[to] = score[i] + sc
                rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 15 11:42:36 2018

@author: maezawa
"""

n, m = list(map(int, input().split()))
score = [-10**13]*(n+1)
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(2*n): 
    rev = 0
    for i in range(1,n+1):
        for (edge, sc) in routes[i]:
            if score[edge] < score[i] + sc:
                score[edge] = score[i] + sc
                rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
score = [-10**13]*(n+1)
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n+1): 
    rev = 0
    for i in range(1,n+1):
        for (edge, sc) in routes[i]:
            if score[edge] < score[i] + sc:
                score[edge] = score[i] + sc
                rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
score = [-10**13]*(n+1)
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n): 
    rev = 0
    for i in range(1,n+1):
        for (edge, sc) in routes[i]:
            if score[edge] < score[i] + sc:
                score[edge] = score[i] + sc
                rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 15 11:42:36 2018

@author: maezawa
"""

n, m = list(map(int, input().split()))
score = [-10**9]*(n+1)
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n): 
    rev = 0
    for i in range(1,n+1):
        for (edge, sc) in routes[i]:
            if score[edge] < score[i] + sc:
                score[edge] = score[i] + sc
                rev += 1
    if rev == 0:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))

d = [-10**13 for i in range(n)]
flag = [0 for i in range(n)]
flag[0] = 1
d2 = [-10**13 for i in range(n)]
flag2 = [0 for i in range(n)]
flag2[0] = 1

for i in range(n):
    for j in range(m):
        if flag[x[j][0] - 1]:
            d[x[j][1] - 1] = max(d[x[j][1] - 1], d[x[j][0] - 1] + x[j][2])
            flag[x[j][1]-1] = 1

for i in range(2*n+1):
    for j in range(m):
        if flag2[x[j][0] - 1]:
            d2[x[j][1] - 1] = max(d2[x[j][1] - 1], d2[x[j][0] - 1] + x[j][2])
            flag2[x[j][1] - 1] = 1

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))

d = [0 for i in range(n)]
flag = [0 for i in range(n)]
flag[0] = 1
d2 = [0 for i in range(n)]
flag2 = [0 for i in range(n)]
flag2[0] = 1

for i in range(n):
    for j in range(m):
        if flag[x[j][0] - 1]:
            d[x[j][1] - 1] = max(d[x[j][1] - 1], d[x[j][0] - 1] + x[j][2])
            flag[x[j][1]-1] = 1

for i in range(2*n+1):
    for j in range(m):
        if flag2[x[j][0] - 1]:
            d2[x[j][1] - 1] = max(d2[x[j][1] - 1], d2[x[j][0] - 1] + x[j][2])
            flag2[x[j][1] - 1] = 1

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))

d = [0 for i in range(n)]
flag = [0 for i in range(n)]
flag[0] = 1
d2 = [0 for i in range(n)]
flag2 = [0 for i in range(n)]
flag2[0] = 1

for i in range(n):
    for j in range(m):
        if flag[x[j][0] - 1]:
            d[x[j][1] - 1] = max(d[x[j][1] - 1], d[x[j][0] - 1] + x[j][2])

for i in range(2*n+1):
    for j in range(m):
        if flag2[x[j][0] - 1]:
            d2[x[j][1] - 1] = max(d2[x[j][1] - 1], d2[x[j][0] - 1] + x[j][2])

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))

d = [0 for i in range(n)]
d2 = [0 for i in range(n)]

for i in range(n):
    for j in range(m):
        d[x[j][1]-1] = max(d[x[j][1]-1], d[x[j][0]-1] + x[j][2])

for i in range(2*n+1):
    for j in range(m):
        d2[x[j][1]-1] = max(d2[x[j][1]-1], d2[x[j][0]-1] + x[j][2])

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
es = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,cost in es:
        fr,to = fr-1,to-1
        cost *= -1
        if d[fr] != INF and d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1:
                print('inf')
                exit()
print(-d[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

edge = [[] for _ in range(n)]
cost = {}

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

d = [inf for _ in range(n)]
d[0] = 0
cnt = 0
while cnt<n:
    update = False
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                update = True
    if not update:
        break
    cnt += 1
# print(d)
if cnt==n:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = 10**10
n,m = map(int, input().split())

edge = [[] for _ in range(n)]
cost = {}

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

d = [inf for _ in range(n)]
d[0] = 0
cnt = 0
while cnt<n:
    update = False
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                update = True
    if not update:
        break
    cnt += 1
# print(d)
if cnt==n:
    print("inf")
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for frm, node in enumerate(graph):
            for cost, to in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdate = True
            
        if cnt == n+1:
            return "inf"
        
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

Submission status: Wrong Answer

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdated = True
    cnt = 0
    while hasUpdated:
        hasUpdated = False
        cnt += 1
        
        for to, node in enumerate(graph):
            for cost, frm in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdated = True
                    
        if cnt == n:
            return "inf"
    
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[b].append((c,a))
    
ans = bf(graph)
print(ans)

Submission status: Wrong Answer

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for to, node in enumerate(graph):
            for cost, frm in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdate = True
                    
        if cnt == 2*n:
            return "inf"
    
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[b].append((c,a))
    
ans = bf(graph)
print(ans)

Submission status: Wrong Answer

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for to, node in enumerate(graph):
            for cost, frm in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdate = True
                    
        if cnt == n+1:
            return "inf"
    
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[b].append((c,a))
    
ans = bf(graph)
print(ans)

Submission status: Wrong Answer

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


class BellmanFord(object):
    def __init__(self, edges, n_nodes, start):
        self.edges = edges
        self.N = n_nodes

        self.dist = [float('inf')] * N
        self.dist[start] = 0
        self.prev = [None] * N

        for _ in range(N - 1):
            for u, v, weight in self.edges:
                if self.dist[u] == float('inf'):
                    continue
                if self.dist[v] > self.dist[u] + weight:
                    self.dist[v] = self.dist[u] + weight
                    self.prev[v] = u

    def check(self, goal=None):
        if goal is None:
            for u, v, weight in self.edges:
                if self.dist[v] > self.dist[u] + weight:
                    return False
            return True
        else:
            negative = [False] * N
            for _ in range(N):
                for u, v, weight in self.edges:
                    if self.dist[u] == float('inf'):
                        continue
                    if self.dist[v] > self.dist[u] + weight:
                        negative[v] = True
                    if negative[u]:
                        negative[v] = True
            return negative[goal]


edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a - 1, b - 1, -c)

bf = BellmanFord(edges, N, 0)
if bf.check(N - 1):
    print(-bf.dist[N - 1])
else:
    print('inf')

Submission status: Wrong Answer

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


class BellmanFord(object):
    def __init__(self, edges, n_nodes, start):
        self.edges = edges
        self.N = n_nodes

        self.dist = [float('inf')] * N
        self.dist[start] = 0
        self.prev = [None] * N

        for _ in range(N - 1):
            for u, v, weight in self.edges:
                if self.dist[u] == float('inf'):
                    continue
                if self.dist[v] > self.dist[u] + weight:
                    self.dist[v] = self.dist[u] + weight
                    self.prev[v] = u

    def check(self, goal=None):
        if goal:
            for u, v, weight in self.edges:
                if self.dist[v] > self.dist[u] + weight:
                    return False
            return True
        else:
            negative = [False] * N
            for _ in range(N):
                for u, v, weight in self.edges:
                    if self.dist[u] == float('inf'):
                        continue
                    if self.dist[v] > self.dist[u] + weight:
                        negative[v] = True
                    if negative[u]:
                        negative[v] = True
            return negative[goal]


edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a - 1, b - 1, -c)

bf = BellmanFord(edges, N, 0)
if bf.check(N - 1):
    print(-bf.dist[N - 1])
else:
    print('inf')

Submission status: Wrong Answer

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


def bellman_ford(edges, n_nodes, start):
    dist = [float('inf')] * n_nodes
    dist[start] = 0
    prev = [None] * N

    for _ in range(n_nodes - 1):
        for u, v, weight in edges:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                prev[v] = u
    
    for u, v, weight in edges:
        if dist[u] + weight < dist[v]:
            return False
    return dist


edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a - 1, b - 1, -c)

dist = bellman_ford(edges, N, 0)
if dist:
    print(-dist[N - 1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）

'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

def shortest_path(s):
    '''
    ベルマンフォード法：ループをV回回す→負の辺がなければアルゴリズムは停止 (update = Falseのまま）、あればV回回したあとも更新が続く
    :param s: スタート
    :return: 負の辺があればNoneを、なければd = sを始点とする最小距離のリスト　を返す
    '''
    d = [float('inf') for i in range(V)]
    d[s] = 0
    for _ in range(V):
        update = False
        for i in range(E):
            e = nodes[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
    if update:
        return None
    else:
        return d

if not shortest_path(0):
    print('inf')
else:
    print(- shortest_path(0)[V - 1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る

		if not upd8: #なにも更新しなかったら終わり
			return Costs[Goal]
			
		if i == N-1: #N-1ループ目のGoalのCostを記録
			tmp = Costs[Goal]

		upd8s = will_upd8s[:]

	if tmp != Costs[Goal]:
		return -INF
	else:
		return Costs[Goal]

print(-BellmanFord(0,N-1))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[i]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る

		upd8s = will_upd8s[:]
		if not upd8:
			return Costs[Goal] #なにも更新しなかったら終わり
	else: #負回路の検出(もうN回)
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print(-BellmanFord(0,N-1))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		#will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			#if not upd8s[i]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					#will_upd8s[t] = True #更新した点だけ次に見る

		#upd8s = will_upd8s[:]
		#if not upd8: break #なにも更新しなかったら終わり

	if upd8 == True: #N回ループしてまだ更新フラグ立ってる
		return -INF	#->負回路が存在する
	else:
		return Costs[Goal]


ans = BellmanFord(0,N-1)
if ans == -INF:
	print('inf')
else:
	print(-ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N+2): #N回ループ(高々N-1回で収束する)
		#will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			#if not upd8s[i]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					#will_upd8s[t] = True #更新した点だけ次に見る
		#upd8s = will_upd8s[:]
		if not upd8: break #なにも更新しなかったら終わり

	if upd8 == True: #N回ループしてまだ更新フラグ立ってる
		return -INF	#->負回路が存在する
	else:
		return Costs[Goal]


ans = BellmanFord(0,N-1)
if ans == -INF:
	print('inf')
else:
	print(-ans)