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:
# -*- coding:utf-8 -*-
class BellmanFord():
    """ベルマンフォード法で最短経路を求める"""
    def __init__(self, s, V):
        """
        Args:
            s(int): 始点
            V(int): 頂点数
        """
        self.graph = {}
        for i in range(V):
            self.graph[i] = []
        self._V = V
        self.dst = [float("inf") for _ in range(V)]
        self.dst[s] = 0

    @property
    def dist(self):
        return self.dst

    @property
    def V(self):
        return self._V

    def add(self, a, b, cost):
        """頂点aから頂点bへのコストはcost"""
        self.graph[a].append((b, cost))

    def shortest_path(self):
        """始点sからの最短経路を求める
        Returns:
            (bool): 負の閉路が存在する(True) / 存在しない(False)
        """
        for t in range(self.V):
            update = False
            for u in range(self.V):
                if self.dst[u] == float("inf"): continue
                for v, cost in self.graph[u]:
                    if self.dst[v] > self.dst[u] + cost:
                        self.dst[v] = self.dst[u] + cost
                        update = True

                        if t == self.V-1:
                            return True

            if not update:
                break

        return False


def solve():
    N, M = map(int, input().split())
    bf = BellmanFord(0, N)

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

    nloop = bf.shortest_path()

    if nloop:
        print("inf")
    else:
        print(-bf.dist[N-1])


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def bellmanford(s, n, es):
    # 負の経路の検出
    # n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    neg = [False]*n
    d[s] = 0

    for i in range(n):
        for p, q, r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    neg[q] = True
    return d, neg


n, w = map(int, input().split())  # n:頂点数　w:辺の数
es = []

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

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

Submission status: Wrong Answer

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

INF = float('inf')
a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [INF]*n
point[0] = 0

for j in range(n):
  for i in range(m):
    
    if point[a[i][0]-1] != INF and point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1) and a[i][1]-1 == (n-1):
        point[a[i][1]-1] = INF
        
        
if INF in point:
  print('inf')
else:
  print((-1)*point[n-1])

Submission status: Wrong Answer

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

INF = float('inf')
a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + [INF]*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][0]-1] != INF and point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1):
        point[a[i][1]-1] = INF
        
        
if INF in point:
  print('inf')
else:
  print((-1)*point[n-1])

Submission status: Wrong Answer

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

INF = float('inf')
a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + [INF]*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][0]-1] != INF and point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1) and a[i][1]-1 == (n-1):
        point[a[i][1]-1] = INF
        
        
if INF in point:
  print('inf')
else:
  print((-1)*point[n-1])

Submission status: Wrong Answer

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

INF = float('inf')
a = [[a[i][0], a[i][1], a[i][2]*(-1)] for i in range(m)]
point = [0] + [INF]*(n-1)

for j in range(n):
  for i in range(m):
    
    if point[a[i][0]-1] != INF and point[a[i][1]-1] > point[a[i][0]-1] + a[i][2]:
      point[a[i][1]-1] = point[a[i][0]-1] + a[i][2]
    
      if j == (n-1) and a[i][1]-1 == (n-1):
        point.append(INF)
        
        
if INF in point:
  print(INF)
else:
  print(-point[n-1])

Submission status: Wrong Answer

Solution code:
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [10**10] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return []
    return d


#############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [[] for i in range(w)] #es[i]: [辺の始点,辺の終点,辺のコスト]
for i in range(w):
    x,y,z = map(int,input().split())
    es[i] = [x-1,y-1,-z]
fnl=find_negative_loop(n,w,es)
if len(fnl)==0:
    print('inf')
else:
    print(-fnl[-1])

Submission status: Wrong Answer

Solution code:
#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return True
    return False

def shortest_path(s,n,w,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について [from,to,cost]
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d
#############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [[] for i in range(w)] #es[i]: [辺の始点,辺の終点,辺のコスト]
for i in range(w):
    x,y,z = map(int,input().split())
    es[i] = [x-1,y-1,-z]

if not find_negative_loop(n,w,es):
    print(-shortest_path(0,n,w,es)[-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return []
    return d


#############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [[] for i in range(w)] #es[i]: [辺の始点,辺の終点,辺のコスト]
for i in range(w):
    x,y,z = map(int,input().split())
    es[i] = [x-1,y-1,-z]
fnl=find_negative_loop(n,w,es)
if len(fnl)==0:
    print('inf')
else:
    print(-fnl[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = dict()

    def add_edge(self, _from, _to, _cost):
        self.edge[(_from, _to)] = _cost

    def fill_cost(self):
        negative_loops = set()
        for i in range(self.n):
            for (_from, _to), _cost in self.edge.items():
                if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                    self.cost[_to] = self.cost[_from] + _cost
                    if i == self.n - 1:
                        negative_loops.add(_to)
        return negative_loops


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

negative_loops = bf.fill_cost()
# print(negative_loops, bf.cost)
if N - 1 in negative_loops:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = dict()

    def add_edge(self, _from, _to, _cost):
        self.edge[(_from, _to)] = _cost

    def fill_cost(self):
        for i in range(self.n + 1):
            for (_from, _to), _cost in self.edge.items():
                if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                    self.cost[_to] = self.cost[_from] + _cost
                    if i == self.n and self.cost[_to] != INF:
                        return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = dict()

    def add_edge(self, _from, _to, _cost):
        self.edge[(_from, _to)] = _cost

    def fill_cost(self):
        for i in range(self.n):
            for (_from, _to), _cost in self.edge.items():
                if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                    self.cost[_to] = self.cost[_from] + _cost
                    if i == self.n - 1:
                        return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys
#DEBUG
sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = collections.defaultdict(dict)

    def add_edge(self, _from, _to, _cost):
        self.edge[_from][_to] = _cost

    def fill_cost(self):
        for i in range(self.n):
            for _from, _edge in self.edge.items():
                for _to, _cost in _edge.items():
                    if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                        self.cost[_to] = self.cost[_from] + _cost
                        if i == self.n - 1:
                            return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if False and not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = collections.defaultdict(dict)

    def add_edge(self, _from, _to, _cost):
        self.edge[_from][_to] = _cost

    def fill_cost(self):
        for i in range(self.n):
            for _from, _edge in self.edge.items():
                for _to, _cost in _edge.items():
                    if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
                        self.cost[_to] = self.cost[_from] + _cost
                        if i == self.n - 1:
                            return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = collections.defaultdict(dict)

    def add_edge(self, _from, _to, _cost):
        self.edge[_from][_to] = _cost

    def fill_cost(self):
        for i in range(self.n):
            for _from, _edge in self.edge.items():
                for _to, _cost in _edge.items():
                    if self.cost[_to] > self.cost[_from] + _cost:
                        self.cost[_to] = self.cost[_from] + _cost
                        if i == self.n - 1 and self.cost[_to] < INF / 2:
                            return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = collections.defaultdict(dict)

    def add_edge(self, _from, _to, _cost):
        self.edge[_from][_to] = _cost

    def fill_cost(self):
        for i in range(self.n+1):
            for _from, _edge in self.edge.items():
                for _to, _cost in _edge.items():
                    if self.cost[_to] > self.cost[_from] + _cost:
                        self.cost[_to] = self.cost[_from] + _cost
                        if i == self.n :
                            return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, M = lmi()
ABC = llmi(M)


class BellmanFord:
    def __init__(self, n, start=0):
        self.n = n
        self.cost = [INF] * n
        self.cost[start] = 0
        self.edge = collections.defaultdict(dict)

    def add_edge(self, _from, _to, _cost):
        self.edge[_from][_to] = _cost

    def fill_cost(self):
        for i in range(self.n):
            for _from, _edge in self.edge.items():
                for _to, _cost in _edge.items():
                    if self.cost[_to] > self.cost[_from] + _cost:
                        self.cost[_to] = self.cost[_from] + _cost
                        if i == self.n - 1:
                            return False  # find negative loop
        return True


bf = BellmanFord(N)
for a, b, c in ABC:
    bf.add_edge(a - 1, b - 1, -c)

flag = bf.fill_cost()
if not flag:
    print('inf')
else:
    print(-bf.cost[-1])

Submission status: Wrong Answer

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1:return True
        return False

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    ok = bf.findneg(N,E)
    if ok:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        neg = [False for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] == INF:continue
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    neg[v] = True
                    if i == V-1:
                        neg[-1] = True
                        return neg[-1]
                if neg[u]:neg[v] = True
        return neg[-1]

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    ok = bf.findneg(N,E)
    if ok:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1:return True

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    ok = bf.findneg(N,E)
    if ok:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        neg = [False for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] == INF:continue
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    neg[v] = True
                if neg[u]:
                    neg[v] = True 
        return neg

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    neg = bf.findneg(N,E)
    if neg[-1]:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist

    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1:return True

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    if bf.findneg(N,E):
        print('inf')
    else:
        ans = bf.bellmanford(0,N,E)
        print(-ans[-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

INF = 10 ** 15
ans = -INF


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    
    def dfs(node, score_sum, _memo):
        memo = deepcopy(_memo)
        if memo[node] != -INF:
            if memo[node] < score_sum:
                print('inf')
                exit()
        else:
            memo[node] = score_sum
            if node == N - 1:
                global ans
                ans = max(ans, score_sum)
            for child, score in graph[node]:
                dfs(child, score_sum + score, memo)
    
    searched = [-INF] * N
    dfs(0, 0, searched)
    
    global ans
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

INF = 10 ** 15
ans = -INF


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    
    def dfs(node, score_sum, memo):
        if memo[node] != -INF:
            if memo[node] < score_sum:
                print('inf')
                exit()
        else:
            memo[node] = score_sum
            if node == N - 1:
                global ans
                ans = max(ans, score_sum)
            for child, score in graph[node]:
                dfs(child, score_sum + score, memo)
    
    searched = [-INF] * N
    dfs(0, 0, searched)
    
    global ans
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    
    INF = 10 ** 15
    searched = [-INF] * N
    
    def dfs(node, score_sum):
        if searched[node] != -INF:
            if searched[node] < score_sum:
                print('inf')
                exit()
        else:
            searched[node] = score_sum
            for child, score in graph[node]:
                dfs(child, score_sum + score)
    
    dfs(0, 0)
    print(searched[-1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

costs = [-(10**20)]*N
costs[0] = 0

epoch = 0
update_number = 1

while update_number > 0 and epoch < N:
    update_number = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            update_number += 1
    epoch += 1

if epoch == N and update_number > 0:
    print('inf')
else:
    print(costs[N-1])

Submission status: Wrong Answer

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

costs = [-(10**20)]*N
costs[0] = 0

epoch = 0
update_number = 1

while update_number > 0 and epoch < N+1:
    update_number = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            update_number += 1
    epoch += 1

if epoch > N:
    print('inf')
else:
    print(costs[N-1])

Submission status: Wrong Answer

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

costs = [-(10**11)]*N
costs[0] = 0

epoch = 0
update_number = 1

while update_number > 0 and epoch < N+1:
    update_number = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            update_number += 1
    epoch += 1

if epoch > N:
    print('inf')
else:
    print(costs[N-1])

Submission status: Wrong Answer

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

costs = [-(10**11)]*N
costs[0] = 0

update_number = 0
L = 1

while L > 0 and update_number <= min(N-1,M)+1:
    L = 0
    for side in sides:
        if costs[side[1]-1] < costs[side[0]-1]+side[2]:
            costs[side[1]-1] = costs[side[0]-1]+side[2]
            L = 1
    update_number += 1

if update_number > min(N-1,M)+1:
    print('inf')
else:
    print(costs[N-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
            if z == n:
                print('inf')
                exit()
print(-dis[n-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
    if not update:
        break

if z == n:
    print('inf')
else:
    print(-dis[n-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
    if not update:
        break

if z == n-1:
    print('inf')
else:
    print(-dis[n-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(2 * n):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
    if not update:
        break

if z == 2 * n-1:
    print('inf')
else:
    print(-dis[n-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
    if not update:
        break

if z == n:
    print('INF')
else:
    print(-dis[n-1])