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:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

import numpy as np
from scipy.sparse import *

N, M = ri_()
a, b, c = [[0] * M for _ in range(3)]
for i in range(M):
    s, t, u = ri_()
    a[i], b[i], c[i] = s - 1, t - 1, -u 
G = csr_matrix((c, (a, b)), shape=(N, N))
try:
    print(-1 * int(csgraph.bellman_ford(G, indices=0)[N - 1]))
except csgraph._shortest_path.NegativeCycleError:
    print('inf')

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = []

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

    dist = [INF] * n
    dist[0] = 0

    for i in range(n - 1):
        for a, b, c in edge:
            dist[b] = min(dist[b], dist[a] + c)

    loop = [False] * n
    for i in range(n):
        for a, b, c in edge:
            if dist[b] > dist[a] + c:
                loop[b] = True

    if loop[n - 1]:
        print("inf")
    else:
        print(-dist[n - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  G[u].append((v, -c))

INF = 10**18
dist = [INF] * (N + 1)
dist[1] = 0
update = 1
for _ in range(N + 1):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
  print("inf")
  exit(0)
print(-dist[N])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# from, to, cost
edges = [list(map(int, input().split())) for _ in range(m)]

score = [-float('inf')] * (n+1)
score[1] = 0
cnt = 0

while True:
    update = False
    cnt += 1
    if cnt == m:
        if score[n] < 0:
            print(score[n])
        else:
            print('inf')
        break

    for e in edges:
        if score[e[0]] != -float('inf') and score[e[1]] < score[e[0]] + e[2]:
            score[e[1]] = score[e[0]] + e[2]
            update = True

    if not update:
        print(score[n])
        break

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
# from, to, cost
edges = [list(map(int, input().split())) for _ in range(m)]

score = [-float('inf')] * (n+1)
score[1] = 0
cnt = 0

while True:
    update = False
    cnt += 1
    if cnt == m:
        print('inf')
        break

    for e in edges:
        if score[e[0]] != -float('inf') and score[e[1]] < score[e[0]] + e[2]:
            score[e[1]] = score[e[0]] + e[2]
            update = True

    if not update:
        print(score[n])
        break

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [-float("inf")]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] < d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1:
            return "inf"
    return d[n-1]

n, w = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x-1, y-1, z])
    #g.append([y, x, z]) # 有向グラフでは削除
print(bellman_ford(0))

Submission status: Wrong Answer

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

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

edge.sort()

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(2 * N + 2):
    for e in edge:
        n, nn, c = e[0], e[1], e[2]
        cost[nn] = max(cost[nn], cost[n] + c)
    if i == N - 1:
        tmp_result = cost[:]

cycle = not all([x == y for x, y in zip(cost, tmp_result)])

print("inf" if cycle else cost[N])

Submission status: Wrong Answer

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

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

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(2 * N + 2):
    for e in edge:
        n, nn, c = e[0], e[1], e[2]
        cost[nn] = max(cost[nn], cost[n] + c)
    if i == N - 1:
        tmp_result = cost[:]

cycle = not all([x == y for x, y in zip(cost, tmp_result)])

print("inf" if cycle else cost[N])

Submission status: Wrong Answer

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

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

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(2 * N + 1):
    for e in edge:
        n, nn, c = e[0], e[1], e[2]
        cost[nn] = max(cost[nn], cost[n] + c)
    if i == N - 1:
        tmp_result = cost[:]

cycle = not all([x == y for x, y in zip(cost, tmp_result)])

print("inf" if cycle else cost[N])

Submission status: Wrong Answer

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

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

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N + 1):
    for e in edge:
        n, nn, c = e[0], e[1], e[2]
        cost[nn] = max(cost[nn], cost[n] + c)
    if i == N - 1:
        tmp_result = cost[:]

cycle = not all([x == y for x, y in zip(cost, tmp_result)])

print("inf" if cycle else cost[N])

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int, ipt().split())
        way[a].append((b,-c))

    def bellmanford(s,g,way):
        n = len(way)
        d = [10**18]*(n)
        d[s] = 0
        sl = 0
        re = True
        while re:
            re = False
            for i in range(1,n):
                for j,cj in way[i]:
                    if d[j] > d[i]+cj:
                         d[j] = d[i]+cj
                         re = True
            sl += 1
            if sl == n:
                d[g] = -10**18
                break
        return d[g]

    ans = bellmanford(1,n,way)
    if ans == -10**18:
        print("inf")
    else:
        print(-ans)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = []
for _ in range(M):
    s,t,d = map(int,input().split())
    edges.append((s,t,d))

cost = [-1*float("INF") for _ in range(N+1)]
cost[1] = 0
count = 0
while True:
    count += 1
    if count > 3*N:
        print("inf")
        exit()
    flag = False
    for s,t,d in edges:
        if cost[s] + d > cost[t]:
            flag = True
            cost[t] = cost[s] + d
    if flag != True:
        break
print(cost[N])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0
enable = [False]*(N+1)
enable[1] = True
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N+1:
        print("inf")
        exit()
    for a,b,c in edges:
        if dp[b] < dp[a]+c:
            flag = True
            dp[b] = dp[a]+c
            if enable[a]==True:
                enable[b]=True
if enable[N]==True:
    print(dp[N])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0
enable = [False]*(N+1)
enable[1] = True
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N+1:
        print("inf")
        exit()
    for a,b,c in edges:
        if dp[b] < dp[a]+c:
            flag = True
            dp[b] = dp[a]+c
            if enable[a]==True:
                enable[b]==True
if enable[N]==True:
    print(dp[N])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0
enable = [False]*(N+1)
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N+1:
        print("inf")
        exit()
    for a,b,c in edges:
        if dp[b] < dp[a]+c:
            flag = True
            dp[b] = dp[a]+c
            if enable[a]==True:
                enable[b]==True
if enable[N]==True:
    print(dp[N])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N+1:
        print("inf")
        exit()
    for a,b,c in edges:
        if dp[b] < dp[a]+c:
            flag = True
            dp[b] = max(dp[b],dp[a]+c)

print(dp[N])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(M)]
dp = [-1*float("INF")]*(N+1)
dp[1] = 0
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N:
        print("inf")
        exit()
    for a,b,c in edges:
        if dp[b] < dp[a]+c:
            flag = True
            dp[b] = max(dp[b],dp[a]+c)

print(dp[N])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
#g=[[]for _ in range(n)]
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[a-1,b-1,-c] for a,b,c in abc]
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和
  for i in range(num_v+1):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1: return -1
  return dist

c=BellmanFord(abc,n,0)
if c==-1:
  print('inf')
else:
  print(-c[n-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
#g=[[]for _ in range(n)]
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[a-1,b-1,-c] for a,b,c in abc]
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1: return -1
  return dist

c=BellmanFord(abc,n,0)
if c==-1:
  print('inf')
else:
  print(-c[n-1])

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i>=n:
                    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*3):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i==n*2-1:
                    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i==n-1:
                    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n+1):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True

        ## 更新されなくなった時点で終了
        if not update:
            break

        if i == n :
            return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
                if i >= n:
                    return -1

        ## 更新されなくなった時点で終了
        if not update:
            break

        if i == n - 1:
            return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n):
        #update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                #update = True
                if i >= n:
                    return -1

        ## 更新されなくなった時点で終了
        #if not update:
        #    break

        #if i >= n - 1:
        #    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        ## 更新されなくなった時点で終了
        if not update:
            break

        if i >= n:
            return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        #update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                #update = True
                if i >= n:
                    return -1

        ## 更新されなくなった時点で終了
        #if not update:
        #    break

        #if i >= n - 1:
        #    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n):
        #update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
                if i >= n:
                    return -1

        ## 更新されなくなった時点で終了
        #if not update:
        #    break

        #if i >= n - 1:
        #    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True

        # 更新されなくなった時点で終了
        if not update:
            break

        if i >= n - 1:
            return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n*2):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True

        # 更新されなくなった時点で終了
        if not update:
            break

        if i >= n - 1:
            return -1
    return d

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

ret = bellman_ford(0)

print(ret)
if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    for i in range(n):
        update = False # 更新が行われたか

        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True

        if not update:
            break

        if i == n - 1:
            return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
def bellman_ford(n, edges):
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n-1):
        for c, u, v in edges:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
    for c, u, v in edges:
        if dist[v] > dist[u] + c:
            return True, dist
    return False, dist

N, M = map(int, input().split())
E = [tuple()] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (-c, a-1, b-1)
f, res = bellman_ford(N, E)
if f:
    print('inf')
else:
    print(-res[N-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for j in range(M):
            e = es[j]
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    while True:
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print(-d[N-1])

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def bfs(start):
    queue=deque([start])
    score=[-float("inf")]*N
    score[start]=0
    d=[0]*N
    while queue:
        x=queue.popleft()
        for y in graph[x]:
            score[y]=max(score[y],score[x]+cost[x][y])
            d[y]=d[x]+1
            if d[y]>=2000:
                score[-1]=float("inf")
                return score
            queue.append(y)
    return score

score=bfs(0)
print(score[-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp = [float("INF")]*(N+1)
edges = []
for _ in range(M):
    s,t,c = map(int,input().split())
    c *= -1
    edges.append((s,t,c))
flag = True
cnt = 0
dp[1] = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N:
        print('inf')
        exit()
    for s,t,c in edges:
        if dp[t] > dp[s]+c:
            dp[t] = dp[s]+c
            flag = True

print(dp[-1]*-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dp = [-1*float("INF")]*(N+1)
edges = [list(map(int,input().split())) for _ in range(M)]
flag = True
cnt = 0
dp[1] = 0
while flag:
    flag = False
    cnt += 1
    if cnt > N:
        print('inf')
        exit()
    for s,t,c in edges:
        if dp[t] < dp[s]+c:
            dp[t] = dp[s]+c
            flag = True

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    
score = [None]*n
score[0] = 0
prev = score
for i in range(m+n+3):
    update = False
    for u in range(n):
        if prev[u] is not None:
            for c,v in ns[u]:
                if score[v] is None or score[v]<prev[u]+c:
                    score[v] = prev[u]+c
                    update = True
    if not update:
        print(score[-1])
        break
    prev = score
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    
score = [None]*n
score[0] = 0
prev = score
for i in range(m+3):
    update = False
    for u in range(n):
        if prev[u] is not None:
            for c,v in ns[u]:
                if score[v] is None or score[v]<prev[u]+c:
                    score[v] = prev[u]+c
                    update = True
    if not update:
        print(score[-1])
        break
    prev = score
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    
score = [None]*n
score[0] = 0
prev = score
for i in range(n+3):
    update = False
    for u in range(n):
        if prev[u] is not None:
            for c,v in ns[u]:
                if score[v] is None or score[v]<prev[u]+c:
                    score[v] = prev[u]+c
                    update = True
    if not update:
        print(score[-1])
        break
    prev = score
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*(N+1) # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(N+1):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == N :
            d[0] = -1
    return d

N,M = map(int,input().split())
g = []

for _ in range(M):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, -z])

ans = bellman_ford(1)
if ans[0] == -1 and int(-ans[-1]) > 0:
  print("inf")
else:
  print(int(-ans[-1]))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*(N+1) # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(N+1):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == N :
            return -1
    return d

N,M = map(int,input().split())
g = []

for _ in range(M):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, -z])

ans = bellman_ford(1)
if ans == -1:
  print("inf")
else:
  print(int(-ans[-1]))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*(N+1) # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(N+1):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == N :
            return -1
    return d

N,M = map(int,input().split())
g = []

for _ in range(M):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, -z])

ans = bellman_ford(1)
if ans == -1:
  print("inf")
else:
  print(-ans[-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        e=0
        for x, y, z in g:
            if d[y] > d[x] + z and d[x] != float('inf'):
                d[y] = d[x] + z
                e+=1
        # 負閉路が存在
        if i == n - 1 and e>0 :
            return "inf"
    return (-1)*d[n-1]

n, m = map(int,input().split()) # n:頂点数, w:辺の数
g = []
for k in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        e=0
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                e+=1
        # 負閉路が存在
        if i == n - 1 and e>0 :
            return "inf"
    return (-1)*d[n-1]

n, m = map(int,input().split()) # n:頂点数, w:辺の数
g = []
for k in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1  :
            return "inf"
    return (-1)*d[n-1]

n, m = map(int,input().split()) # n:頂点数, w:辺の数
g = []
for k in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1  :
            return "inf"
    return (-1)*d[n-1]

n, m = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0))

Submission status: Wrong Answer

Solution code:
def bellman_ford(s,k):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1  :
            return "inf"
    return (-1)*d[k]

n, m = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0,n-1))