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:
def BellmanFord():
    def BF(s, n, edge, inf=float("inf")):
        d = [inf for i in range(n)]
        d[s] = 0
        for i in range(n + 1):
            for before, after, dist in edge:
                if before != inf:
                    d[after] = min(d[after], d[before] + dist)
            if i == n - 1:
                t = d[:]
            elif i == n:
                for i, j in enumerate(d):
                    if j != t[i]:
                        d[i] = -inf
        return list(map(lambda x: -x, d))
    n, m = map(int, input().split())
    inf = 10 ** 20
    edge = [list(map(int, input().split())) for i in range(m)]
    edge = [[x - 1, y - 1, -z] for x, y, z in edge]
    l = BF(0, n, edge)
    print(l[-1] if l[-1] < inf else "inf")

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == self.N - 1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(2000):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == 2000 - 1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N + 1):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == self.N:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self):
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s,numEdges):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(numEdges):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == numEdges - 1:
                            return True
        return False

G = BellmanFord()

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1,M):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == self.N - 1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[u] != float('inf') and d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s,numNodes):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(numNodes):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[u] != float('inf') and d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == numNodes -1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1,N):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s,numNodes):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(numNodes):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == numNodes -1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

if G.BellmanFord_negative_bool(1,N):
    print('inf')
    exit()

print(-G.BellmanFord_search(1)[N])

Submission status: Wrong Answer

Solution code:
N,M,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append(b)

ok = [False]*(N+1)
ok[1] = True
q = [1]
while q:
  p = q.pop()
  for v in dic[p]:
    if not ok[v]:
      ok[v] = True
      q.append(v)
cnt = 0
dist = [-10**20]*(N+1)
dist[1] = 0
while True:
  flag = True
  for a,b,c in zip(*[iter(L)]*3):
    if ok[a]&ok[b] and ok[a]!=-10**20 and dist[b]<dist[a]+c:
      flag = False
      dist[b] = dist[a]+c
  if flag:
    print(dist[N])
    break
  cnt += 1
  if cnt>N+10:
    print('inf')
    break

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford

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

try:
  d = bellman_ford(graph)
  print(int(-d[0][-1]))
except:
  print('inf')

Submission status: Wrong Answer

Solution code:
N,M,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append(b)

ok = [False]*(N+1)
ok[1] = True
q = [1]
while q:
  p = q.pop()
  for v in dic[p]:
    if not ok[v]:
      ok[v] = True
      q.append(v)
cnt = 0
dist = [-10**20]*(N+1)
dist[1] = 0
while True:
  flag = True
  for a,b,c in zip(*[iter(L)]*3):
    if ok[a]&ok[b] and ok[a]!=-10**20 and dist[b]<dist[a]+c:
      flag = False
      dist[b] = dist[a]+c
  if flag:
    print(dist[N])
    break
  cnt += 1
  if cnt>N:
    print('inf')
    break

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    for _ in range(N):
        update = False
        for e in ed:
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d, True
    return 0, False

d, j = bellman_ford(N-1)
if j:
    print(-d[0])
else:
    print("in")

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    cnt = 0
    while cnt < N + 5:
        cnt += 1
        update = False
        for i in range(M):
            e = ed[i]
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d, True
    return [INIT] * N, False

d, j = bellman_ford(0)
if j:
    print(-d[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    cnt = 0
    while cnt < N + 5:
        cnt += 1
        update = False
        for i in range(M):
            e = ed[i]
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d
    return [INIT] * N

d = bellman_ford(0)
print(-d[-1] if d[-1] < 10 ** 30 else "inf")

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    '''
    ベルマンフォード法

    Parameters
    s : int
        初期位置
    
    Returns
    d : list
        sからの最短経路のコストを表すリスト
    '''
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    cnt = 0
    while cnt < N * 2:
        cnt += 1
        update = False
        for i in range(M):
            e = ed[i]
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d
    return [INIT] * N

d = bellman_ford(0)
print(-d[-1] if d[-1] < 10 ** 30 else "inf")

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    '''
    ベルマンフォード法

    Parameters
    s : int
        初期位置
    
    Returns
    d : list
        sからの最短経路のコストを表すリスト
    '''
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    cnt = 0
    while cnt < N * 2:
        cnt += 1
        update = False
        for i in range(M):
            e = ed[i]
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d
    return [INIT] * N

d = bellman_ford(0)
print(d[-1] if d[-1] < 10 ** 30 else "inf")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(2000):
        judge = False
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == 2000:
                    judge = True
    return 'inf' if judge else -dist[-1]

print(bellman_ford(edges, N))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(2*n+1):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==2*n:
                print('inf')
                exit()
print(dist[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(n):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==n-1:
                print('inf')
                exit()
print(dist[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(n):
    for a, b, c in edge:
        if dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==n-1:
                print('inf')
                exit()
print(dist[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
NINF = -10**10
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(n):
    for a, b, c in edge:
        if dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==n-1:
                print('inf')
                exit()
print(dist[-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1,b-1
    edge[a].append((b,c))

INF = 10 ** 30

def main():
    if len(edge[N-1]) > 0:
        return INF
    # q = (-スコア、現在地)
    q = []
    d = [0] * N
    used = [False] * N
    heappush(q,(0, 0))
    while len(q) > 0:
        c, v = heappop(q)
        d[v] = c
        for nv, nc in edge[v]:
            heappush(q,(c-nc, nv))
    return -d[N-1]
   
    

ans = main()
print(ans if ans < INF else "inf")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
abc=[]
for i in range(m):
    a,b,c=map(int,input().split())
    abc.append([min(a-1,b-1),max(a-1,b-1),-c])
abc.sort()
INF=10**18
d=[INF]*n
chk=[False]*n
d[0]=0
for i in range(n-1):
    for a,b,c in abc:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
for i in range(n):
    for a,b,c in abc:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            chk[b]=True
            chk[a]=True
if chk[n-1]==True:
    print('inf')
else:
    print(-d[n-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
score = [inf] * (N + 1)
score[1] = 0

for _ in range(N + 1):
    update = False
    for a, b, c in edge:
        if score[b] > score[a] + c:
            score[b] = score[a] + c
            update = True
    if not update:
        break

if update:
    print("inf")
else:
    print(-score[N])

Submission status: Wrong Answer

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

for _ in range(M):
    fr, to, cost = map(int, input().split())
    edges.append((fr - 1, to - 1, -cost))

minDist = [float('inf')] * N
minDist[0] = 0

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N:
                print('inf')
                exit()
            minDist[to] = d

print(-minDist[N - 1])

Submission status: Wrong Answer

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

for _ in range(M):
    fr, to, cost = map(int, input().split())
    edges.append((fr - 1, to - 1, -cost))

minDist = [10**18] * N
minDist[0] = 0

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N:
                print('inf')
                exit()
            minDist[to] = d

print(-minDist[N - 1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
abc=[]
for i in range(m):
    a,b,c=map(int,input().split())
    abc.append([min(a-1,b-1),max(a-1,b-1),-c])
abc.sort()
INF=10**18
d=[INF]*n
d[0]=0
flg,cnt=1,0
while flg==1:
    flg=0
    for a,b,c in abc:
        if d[b]>d[a]+c:
            flg=1
            d[b]=d[a]+c
    cnt+=1
    if cnt>=n:
        flg=1
        break
if flg==0:
    print(-d[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split(' '))
piece=[0]*m
for i in range(m):
    piece[i]=tuple(map(int,input().split(' ')))

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

for v in range(n-1):
    for e in range(m):
        a,b,c=piece[e]
        if node[b-1] > node[a-1]-c:
            node[b-1] = node[a-1]-c
ans=-node[n-1]
nega=[False]*n
for v in range(n):
    for e in range(m):
        a,b,c=piece[e]
        if node[b-1] > node[a-1] - c:
            node[b-1] = node[a-1] -c
            nega[b-1]= True
        if node[a-1]==True:
            node[b-1]=True

if nega[n-1]==True:
    print('inf')
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N+1):
        judge = False
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == N:
                    judge = True
    return 'inf' if judge else -dist[-1]

print(bellman_ford(edges, N))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N):
        judge = False
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == N-1:
                    judge = True
    return 'inf' if judge else -dist[-1]

print(bellman_ford(edges, N))

Submission status: Wrong Answer

Solution code:
#負の経路の検出
def find_negative_loop(n, es):
    d = [float("inf")] * n
    d[0] = 0
    #始点はどこでもよい
    for i in range(n):
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    return True
    return False

def shortest_path(s, n, es):
    #s -> i　の最短経路
    #s: 始点、n: 頂点数、w:辺の数、es[i]: [辺の始点、辺の終点、辺のコスト]
    d = [float("inf")] * n
    #d[i]: s->iの最短距離
    d[s] = 0
    while True:
        update = False
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        # print(update)
        if not update:
            break
    return d

n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]

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

# print(shortest_path(0, n, es))
# print(es)

if find_negative_loop(n,es):
    print("inf")
else:
    d = shortest_path(0, n, es)
    print(-d[-1])

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import bellman_ford

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

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

try:
    dist = bellman_ford(edge)
    print(int(-dist[0][-1]))
except:
    print("inf")

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 > 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())
graph=[[] for i in range(N+1)]
for _ in range(M):
    a,b,weight=map(int,input().split())
    graph[a].append((b,-weight))
    
class Node():
    def __init__(self,name):
        self.name=name
        self.par=None
        self.d=float("inf")
        
    def relax(self,other,weight):
        if self.d>other.d+weight:
            self.d=other.d+weight
            self.par=other.name
    def relax_(self,other,weight):
         if self.d>other.d+weight:
            self.d=other.d+weight
            return True
         return False
def bellman_ford(graph,s_node):
    N=len(graph)-1
    d_list=[Node(i) for i in range(N+1)]
    #初期化
    d_list[s_node].d=0
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)
    negative=[False for i in range(N+1)]
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                if d_list[point].relax(d_list[node],distance):
                    if negative[point]==False:
                        negative[point]=True
                    else:
                        for que in graph[point]:
                            negative[que[0]]=True
    if negative[N]:
        return False

    return d_list[N].d

K=bellman_ford(graph,1)
if K!=False:
    print(-K)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
graph=[[] for i in range(N+1)]
for _ in range(M):
    a,b,weight=map(int,input().split())
    graph[a].append((b,-weight))
    
class Node():
    def __init__(self,name):
        self.name=name
        self.par=None
        self.d=float("inf")
        
    def relax(self,other,weight):
        if self.d>other.d+weight:
            self.d=other.d+weight
            self.par=other.name
            
def bellman_ford(graph,s_node):
    N=len(graph)-1
    d_list=[Node(i) for i in range(N+1)]
    #初期化
    d_list[s_node].d=0
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)
    NOW=d_list[N].d
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)
    if NOW!=d_list[N].d:
        return False
    for  node in range(1,N+1):
        for tuple_ in graph[node]:
            point,distance=tuple_
            if d_list[point].d>d_list[node].d+distance:
                return False
    return d_list  

K=bellman_ford(graph,1)
if K!=False:
    print(-K[N].d)
else:
    print("inf")