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:
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 False
        return self.dist

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)

d = bf.build()
if d != False:
    print(- d[n-1])
else:
    print('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 False
        return True

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)

flag = bf.build()
if flag:
    print(- bf.dist[n-1])
else:
    print('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 False
        return True

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)

if bf.build():
    print(-bf.dist[n-1])
else:
    print('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 False
        return True

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)

if bf.build():
    print(-bf.dist[n-1])
else:
    print('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):
            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 False
        return True

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)

if bf.build():
    print(-bf.dist[n-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
array = [tuple(int(x) for x in input().split()) for x in range(M)]
score = [-float("inf") for x in range(N)]
score[0] = 0
while(True):
    if(N < 0):
        print("inf")
        break
    now = score.copy()
    for j in array:
        if(score[j[0]-1] + j[2] > score[j[1]-1]):
            score[j[1]-1] = score[j[0]-1] + j[2]
    if(now == score):
        print(score[-1])
        break
    N += -1

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[e[0]] or negative[e[1]]:
        negative[e[0]] = 1
        negative[e[1]] = 1
if negative[N]:
    print('inf')
else:
    print(-d[N])

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                print('inf')
                sys.exit()
print(-d[N])

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = 10 ** 8
d = [INF for _ in range(N+1)]
d[1] = 0
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                print('inf')
                sys.exit()
print(-d[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(2*n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1:
                        return -1
    return dist

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i == n - 1:
                        return -1
    return dist

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = -1 * abc[i][2]
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c
# print(abc)

# def BellmanFord(edges,num_v,source):
#     #グラフの初期化
#     inf = float("inf")
#     dist = [ inf for i in range(num_v) ]
#     dist[source] = 0
#     #辺の緩和
#     for i in range(num_v):
#         for edge in edges:
#             if edge[0]!=inf and dist[edge[1]]>(dist[edge[0]]+edge[2]):
#                 dist[edge[1]] = dist[edge[0]] + edge[2]
#                 if i==(num_v-1):
#                     return False,[]
#     return True,dist

# sからiへの最短距離を求める（Bellman-Ford法）
# s:始点，n:頂点数，w:辺の数，es[i]:[辺の始点,辺の終点,辺のコスト]
def BellmanFord(s,n,w,es):
    # 初期化
    d = [float("inf")]*n
    d[s] = 0
    # 更新
    for i in range(n):
        # update = False
        for p,q,r in es:
            # [p,q,r] = [from, to, cost]
            if d[p]!=float("inf") and d[q]>(d[p]+r):
                d[q] = d[p] + r
                # update = True
                if i==(n-1):
                    return False,[]
        # if update:
        #     pass
        # else:
        #     break
    return True,d

# def find_negative_loop(s,n,w,es):
#     #負の経路の検出
#     #n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
#     d = [float("inf")] * n
#     d[s] = 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

flag,distance = BellmanFord(0,n,m,abc)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = -1 * abc[i][2]
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c
# print(abc)

# def BellmanFord(edges,num_v,source):
#     #グラフの初期化
#     inf = float("inf")
#     dist = [ inf for i in range(num_v) ]
#     dist[source] = 0
#     #辺の緩和
#     for i in range(num_v):
#         for edge in edges:
#             if edge[0]!=inf and dist[edge[1]]>(dist[edge[0]]+edge[2]):
#                 dist[edge[1]] = dist[edge[0]] + edge[2]
#                 if i==(num_v-1):
#                     return False,[]
#     return True,dist

# sからiへの最短距離を求める（Bellman-Ford法）
# s:始点，n:頂点数，w:辺の数，es[i]:[辺の始点,辺の終点,辺のコスト]
def BellmanFord(s,n,w,es):
    # 初期化
    d = [float("inf")]*n
    d[s] = 0
    # 更新
    for i in range(n):
        update = False
        for p,q,r in es:
            # [p,q,r] = [from, to, cost]
            if d[p]!=float("inf") and d[q]>(d[p]+r):
                d[q] = d[p] + r
                update = True
                if i==(n-1):
                    return False,[]
        if update:
            pass
        else:
            break
    return True,d

# def find_negative_loop(s,n,w,es):
#     #負の経路の検出
#     #n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
#     d = [float("inf")] * n
#     d[s] = 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

flag,distance = BellmanFord(0,n,m,abc)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = abc[i][2] * (-1)
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c
# print(abc)

def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf = float("inf")
    dist = [ inf for i in range(num_v)]
    dist[source] = 0
    
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]]>(dist[edge[0]]+edge[2]):
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==(num_v-1):
                    return False,[]
    return True,dist

flag,distance = BellmanFord(abc,n,0)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def bellman_ford(edges, size, source):
    dist = [float('inf')] * size
    dist[source] = 0
    for _ in range(size):
        update = False
        for u, v, weight in edges:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                update = True
        if not update:
            break
    return dist

def find_negative_loop(edges, size, source):
    dist = [0] * size
    for i in range(size):
        for u, v, weight in edges:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                if i == size - 1:
                    return True
    return False

N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))
if find_negative_loop(edges, N+1, 1):
    print('inf')
else:
    dist = bellman_ford(edges, N+1, 1)
    print(-dist[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

# returns None if the graph contains a negative cycle
def bellman_ford(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    for i in range(size):
        for u, v, weight in edges:
            if distance[v] > distance[u] + weight:
                distance[v] = distance[u] + weight
                if i == size - 1:
                    return None
    return distance

N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))
dist = bellman_ford(edges, N, 0)
print(-dist[N-1] if dist else 'inf')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

# returns None if the graph contains a negative cycle
def bellman_ford(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    for i in range(size):
        for u, v, weight in edges:
            if distance[u] < float('inf') and distance[v] > distance[u] + weight:
                distance[v] = distance[u] + weight
                if i == size - 1:
                    return None
    return distance

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

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

Submission status: Wrong Answer

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

stack = [0]
can_reach = [0]*n
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)

INF = 10**10
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1


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

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # make graph
    G = [set() for _ in range(N)]
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G[E[i][0]].add(E[i][1])

    def bfs(s):
        # find connected vertex by bfs
        vis_loc = [False] * N
        vis_loc[s] = True
        q = deque([s])
        while len(q):
            v = q.popleft()
            for n in G[v]:
                if vis_loc[n]:
                    continue
                q.append(n)
                vis_loc[n] = True
        return vis_loc

    vis = bfs(0)
    C = []
    for i in range(M):
        if vis[E[i][0]]:
            C.append(i)

    # Bellman-Ford
    N_con = sum(vis)
    ans = [float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        ud = -1
        for j in C:
            a, b, c = E[j]
            if ans[b] > ans[a] - c:
                ans[b] = ans[a] - c
                ud = b
        if ud == -1:
            break
        else:
            if i == N_con - 1:
                if bfs(ud)[N - 1]:
                    print('inf')
                    exit()
    print(-ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
negative_cycle = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        if i == n-1:
            negative_cycle = 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # make graph
    G = [set() for _ in range(N)]
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G[E[i][0]].add(E[i][1])

    # find connected vertex by bfs
    vis = [False] * N
    vis[0] = True
    q = deque([0])
    while len(q):
        v = q.popleft()
        for n in G[v]:
            if vis[n]:
                continue
            q.append(n)
            vis[n] = True
    C = []
    for i in range(M):
        if vis[E[i][0]]:
            C.append(i)

    # Bellman-Ford
    N_con = sum(vis)
    ans = [float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        flag = False
        for j in C:
            a, b, c = E[j]
            if ans[b] > ans[a] - c:
                ans[b] = ans[a] - c
                flag = True
        if not flag:
            break
        else:
            if i == N_con - 1:
                print('inf')
                exit()
    print(-ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # make graph
    G = [set() for _ in range(N)]
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G[E[i][0]].add(E[i][1])

    # find connected vertex by bfs
    vis = [False] * N
    vis[0] = True
    q = deque([0])
    while len(q):
        v = q.popleft()
        for n in G[v]:
            if vis[n]:
                continue
            q.append(n)
            vis[n] = True
    C = []
    for i in range(M):
        if vis[E[i][0]]:
            C.append(i)

    # Bellman-Ford
    N_con = sum(vis)
    ans = [-float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        flag = False
        for j in C:
            a, b, c = E[j]
            if ans[b] < ans[a] + c:
                ans[b] = ans[a] + c
                flag = True
        if not flag:
            break
        else:
            if i == N_con - 1:
                print('inf')
                exit()
    print(ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def same(self, x, y):
        return self.root(x) == self.root(y)


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # find connected vertex
    G = UnionFind(N)
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G.unite(E[i][0], E[i][1])
    C = []
    for i in range(M):
        if G.same(0, E[i][0]):
            C.append(i)

    # Bellman-Ford
    N_con = G.size(0)
    E_con = len(C)
    ans = [-float('inf')] * N
    ans[0] = 0
    for i in range(N_con + 1):
        flag = False
        for j in range(E_con):
            a, b, c = E[C[j]]
            if ans[b] < ans[a] + c:
                ans[b] = ans[a] + c
                flag = True
        if not flag:
            break
        else:
            if i == N_con:
                print('inf')
                exit()
    print(ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def same(self, x, y):
        return self.root(x) == self.root(y)


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # find connected vertex
    G = UnionFind(N)
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G.unite(E[i][0], E[i][1])
    C = []
    for i in range(M):
        if G.same(0, E[i][0]):
            C.append(i)

    # Bellman-Ford
    N_con = G.size(0)
    E_con = len(C)
    ans = [-float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        flag = False
        for j in range(E_con):
            a, b, c = E[C[j]]
            if ans[b] < ans[a] + c:
                ans[b] = ans[a] + c
                flag = True
        if not flag:
            break
        else:
            if i == N_con - 1:
                print('inf')
                exit()
    print(ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from scipy.sparse.csgraph import shortest_path, bellman_ford, csgraph_from_dense
import numpy as np

n, m = map(int, input().split())
l = np.full((n, n), None)
edge = [[] for _ in range(n)]
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  l[a, b] = -c
  edge[a].append(b)
  
def dfs():
  stack = []
  seen = [False]*n
  stack.append(0)
  while stack:
    v = stack.pop()
    seen[v] = True
    for nv in edge[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  return seen

seen = dfs()
idx = np.array([i for i in range(n) if seen[i]])
l = l[idx, :]
l = l[:, idx]
G = csgraph_from_dense(l, null_value=None)
try:
  B = bellman_ford(G, indices=[0])
  ans = -int(B[0][-1])
except:
  ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from scipy.sparse.csgraph import shortest_path, bellman_ford, csgraph_from_dense
import numpy as np

n, m = map(int, input().split())
l = np.full((n, n), None)
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  l[a, b] = -c
G = csgraph_from_dense(l, null_value=None)
try:
  B = bellman_ford(G, indices=[0])
  ans = -int(B[0][-1])
except:
  ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from scipy.sparse.csgraph import shortest_path, bellman_ford
import numpy as np

n, m = map(int, input().split())
l = np.zeros((n, n), dtype=np.int64)
G = [[] for _ in range(n)]
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  l[a, b] = -c
  G[a].append(b)
  
def dfs():
  stack = []
  seen = [False]*n
  stack.append(0)
  while stack:
    v = stack.pop()
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  return seen

seen = dfs()
idx = np.array([i for i in range(n) if seen[i]])
l = l[idx, :]
l = l[:, idx]
try:
  B = bellman_ford(l, indices=[0])
  ans = -int(B[0][-1])
except:
  ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, N, start, end):
    cost = [float("inf") for _ in range(N)]
    cost[start] = 0
    for i in range(N):
        for j in range(len(edges)):
            fro, to, c = edges[j]

            if cost[to] > cost[fro] + c:
                cost[to] = cost[fro] + c
                # 頂点の数と同じ回数ループすると負の経路がある
                if i == N - 1:
                    return "inf"
    return -cost[end]


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

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

cost = [float("inf") for _ in range(N)]
start = 0
end = N - 1
print(bellman_ford(edges, N, start, end))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]


#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]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
                if i == n-1:
                    return 0
    return d


#############################
ans=find_negative_loop(n,m,abc)
if ans==0:
    print("inf")
else:
    print(-ans[-1])