Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(2*N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-1:
      t = score[N-1]
    if i == 2*N:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = [float("inf") for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
  for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
      score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
  if score[j[1]] < score[j[0]] + j[2]:
    score[N-1] = 1e+20
if score[N-1] < 1e+20:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
  for j in adjacent:
    if score[j[1]] == 'None' and score[j[0]] != 'None':
      score[j[1]] = score[j[0]] + j[2]
    if score[j[1]] != 'None' and score[j[0]] != 'None':
      if score[j[1]] < score[j[0]] + j[2]:
        score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
  if score[j[1]] != 'None' and score[j[0]] != 'None':
    if score[j[1]] < score[j[0]] + j[2]:
      score[N-1] = 1e+20
if score[N-1] < 1e+20:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
  if score[j[1]] != 'None' and score[j[0]] != 'None':
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = [-2e+15 for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N-1):
    for j in adjacent:
        if score[j[1]] < score[j[0]] + j[2]:
            score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = [-2e+15 for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
        if score[j[1]] < score[j[0]] + j[2]:
            score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjacent = []
score = [-2e+9 for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
        if score[j[1]] < score[j[0]] + j[2]:
            score[j[1]] = score[j[0]] + j[2]
for j in adjacent:
    if score[j[1]] < score[j[0]] + j[2]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(score[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

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

point = ["n"]*n

already = [False]*n
not_yet = deque([0])
point[0] = 0
while not_yet:
  k = not_yet.popleft()
  if already[k]:
    continue
  already[k] = True
  for v in graph[k]:
    v1, v2 = v[0], v[1]
    if already[v1]:
      if point[v1] < point[k]+v2 and 0 < point[k]+v2:
        print("inf")
        sys.exit()
    else:
      if point[v1] != "n":
        point[v1] = max([point[k]+v2, point[v1]])
      else:
        point[v1] = point[k]+v2
      not_yet.append(v1)

print(point[n-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

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

point = ["n"]*n

already = [False]*n
not_yet = deque([0])
point[0] = 0
while not_yet:
  k = not_yet.popleft()
  if already[k]:
    continue
  already[k] = True
  for v in graph[k]:
    v1, v2 = v[0], v[1]
    if already[v1]:
      if point[v1] < point[k]+v2:
        print("inf")
        sys.exit()
    else:
      if point[v1] != "n":
        point[v1] = max([point[k]+v2, point[v1]])
      else:
        point[v1] = point[k]+v2
      not_yet.append(v1)

print(point[n-1])

Submission status: Wrong Answer

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

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

inf = 10**18
d = [inf for i in range(N)]
d[0] = 0
cnt = 0
while True:
    update = False
    for i in range(M):
        e = es[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
    cnt += 1
    if cnt >= N-1:
        break

if cnt >= N-1:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

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

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

inf = 10**18
d = [inf for i in range(N)]
d[0] = 0
cnt = 0
while True:
    update = False
    for i in range(M):
        e = es[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
    cnt += 1
    if cnt >= N+1:
        break

if cnt >= N+1:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

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

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

inf = 10**18
d = [inf for i in range(N)]
d[0] = 0
cnt = 0
while True:
    update = False
    for i in range(M):
        e = es[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
    cnt += 1
    if cnt >= N:
        break

if cnt >= N:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

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

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

inf = 10**18
d = [inf for i in range(N)]
d[0] = 0
cnt = 0
while True:
    update = False
    for i in range(M):
        e = es[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
    cnt += 1
    if cnt >= M:
        break

if cnt >= M:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        if not update:
            break
        cnt+=1
    F=[False]*N
    for j in range(N):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=-INF
                F[t]=True
    if F[N-1]:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[f]!=INF and dist[t]>dist[f]+c:
                dist[t]=min(dist[t],dist[f]+c)
    for j in range(N):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=-INF
    if dist[N-1]==-INF:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
        cnt+=1
        if not update:
            break
    for j in range(N):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=-INF
    if dist[N-1]==-INF:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
        cnt+=1
        if not update:
            break
    for j in range(N-1):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                if t==N-1:
                    print('inf')
                    exit()
                    dist[t]=-INF
    return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        cnt+=1
        if not update:
            break
    if neg:
        for j in range(N):
            for f,t,c in Edge:
                if(dist[t]>dist[f]+c):
                    if t==N-1:
                        print('inf')
                        exit()
                    dist[t]=min(dist[t],dist[f]+c)
    return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        if not update:
            break
        cnt+=1
    F=[False]*N
    for j in range(N+1):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=-INF
                F[t]=True
    if F[N-1]:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        if not update:
            break
        cnt+=1
    F=[False]*N
    if neg:
        for j in range(N):
            for f,t,c in Edge:
                if(dist[t]>dist[f]+c):
                    dist[t]=-INF
                    F[t]=True
    if F[N-1]:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        for j in range(N+1):
            for f,t,c in Edge:
                if(dist[t]>dist[f]+c):
                    dist[t]=-INF
    if(dist[N-1]==-INF):
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Wrong Answer

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
        data[i] *= -1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    try:
        s = shortest_path(a)
        m = -s[0][n - 1]
        print("{}".format(int(m)))
    except scipy.sparse.csgraph.NegativeCycleError:
        print("inf")


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
        data[i] *= -1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    try:
        s = shortest_path(a, indices=0)
        m = -s[n - 1]
        print("{}".format(int(m)))
    except:
        print("inf")


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
        data[i] *= -1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    try:
        s = shortest_path(a, indices=0)
        m = -s[n - 1]
        print("{}".format(int(m)))
    except:
        print("inf")


resolve()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                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 not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i != numNodes:
                        return True
        return False

n,m = na()
g = BellmanFord()

for i in range(m):
    a,b,c = na()
    a,b,c = a-1,b-1,-c
    g.add(a, b, c, directed=True)

if g.BellmanFord_negative_bool(n):
    print('inf')
    exit()

d = g.BellmanFord_search(0)
print(-d[n-1])

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[-INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]<dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=-INF:
                        dist[t]=max(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=INF
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        cnt_=0
        while True:
            if(cnt_>=N-1):
                break
            for f,t,c in Edge:
                if dist[t]<dist[f]+c:
                    dist[t]=INF
            cnt_+=1
    return dist
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,c
    Edge.append([a,b,c])
arr=Bellman_Ford(0,N,Edge)
print(arr[N-1] if arr[N-1]!=INF else 'inf')

Submission status: Wrong Answer

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    dist[t]=-INF
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        cnt_=0
        while True:
            if(cnt_==N-1):
                break
            for f,t,c in Edge:
                if dist[t]>dist[f]+c:
                    dist[t]=-INF
            cnt_+=1
    return dist
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
arr=Bellman_Ford(0,N,Edge)
print(-arr[N-1] if arr[N-1]!=-INF else 'inf')

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                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 not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

n,m = na()
g = BellmanFord()

for i in range(m):
    a,b,c = na()
    a,b,c = a-1,b-1,-c
    g.add(a, b, c, directed=True)

if g.BellmanFord_negative_bool(n-1):
    print('inf')
    exit()

d = g.BellmanFord_search(0)
print(-d[n-1])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                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 not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

n,m = na()
g = BellmanFord()

for i in range(m):
    a,b,c = na()
    a,b,c = a-1,b-1,-c
    g.add(a, b, c, directed=True)

if g.BellmanFord_negative_bool(n):
    print('inf')
    exit()

d = g.BellmanFord_search(0)
print(-d[n-1])

Submission status: Wrong Answer

Solution code:
INF=10**30

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        cnt_=0
        while True:
            if(cnt_==N-1):
                break
            for f,t,c in Edge:
                if dist[t]>dist[f]+c:
                    dist[t]=-INF
            cnt_+=1
    return dist
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
arr=Bellman_Ford(0,N,Edge)
print(-arr[N-1] if arr[N-1]!=-INF else 'inf')

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import copy

n,m = na()
g = [[] for i in range(n)]

for i in range(m):
    a,b,c = na()
    a,b = a-1,b-1
    g[a].append((b,c))

def dfs(k, rr, ss):
    ans = -1000000000000
    for v,c in g[k]:
        s = copy.copy(ss)
        r = rr+c
        if v == k:
            if c > 0:
                print('inf')
                exit()
            continue
        if v in s:
            if r > s[v]:
                print('inf')
                exit()
            else:
                return -100000000000
        s[v] = r
        ans = max(ans,dfs(v,r,s))
        if v == n-1:
            ans = max(ans, r)
    return ans

print(dfs(0, 0, {}))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import copy

n,m = na()
g = [[] for i in range(n)]

for i in range(m):
    a,b,c = na()
    a,b = a-1,b-1
    g[a].append((b,c))

def dfs(k, rr, ss):
    s = copy.copy(ss)
    ans = -1000000000000
    for v,c in g[k]:
        r = rr+c
        if v == k:
            if c > 0:
                print('inf')
                exit()
            continue
        if v in s:
            if r > s[v]:
                print('inf')
                exit()
            else:
                return -100000000000
        s[v] = r
        ans = max(ans,dfs(v,r,s))
        if v == n-1:
            ans = max(ans, r)
    return ans

print(dfs(0, 0, {}))

Submission status: Wrong Answer

Solution code:
INF=10**30

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        cnt_=0
        while True:
            if(cnt_==N):
                break
            for f,t,c in Edge:
                if dist[t]>dist[f]+c:
                    dist[t]=-INF
            cnt_+=1
    return dist
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
arr=Bellman_Ford(0,N,Edge)
print(-arr[N-1] if arr[N-1]!=-INF else 'inf')

Submission status: Wrong Answer

Solution code:
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                return 'inf'
        return -self.dist[n-1]

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

bf = BellmanFord(n,0)

for i in range(m):
    a,b,c = map(int,input().split())
    bf.add(a - 1,b - 1,- c)

print(bf.build())