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:
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    prev = [-1]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = False
        for v in V:
            for u, c in E[v].items():
                temp = dist[v] + c
                if dist[u] > temp:
                    updated = True
                    dist[u] = temp
                    prev[u] = v
        if not updated: # the minimum costs are already stored in dist
            break
    else: # the above loop is not broken if and only if there exists a negative cycle
        return None
    return dist

N, M = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = -c
V = list(range(N))
dist = bellman_ford(V, E, 0)
if dist is None:
    print('inf')
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    prev = [-1]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = False
        for v in V:
            d = dist[v]
            for u, c in E[v].items():
                temp = d + c
                if dist[u] > temp:
                    updated = True
                    dist[u] = temp
                    prev[u] = v
        if not updated: # the minimum costs are already stored in dist
            break
    else: # the above loop is not broken if and only if there exists a negative cycle
        return None
    return dist

N, M = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = -c
V = list(range(N))
dist = bellman_ford(V, E, 0)
if dist is None:
    print('inf')
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = False
        for v in V:
            d = dist[v]
            for u, c in E[v].items():
                temp = d + c
                if dist[u] > temp:
                    updated = True
                    dist[u] = temp
        if not updated: # the minimum costs are already stored in dist
            break
    if n_iterations == N-1: # the above loop is not broken if and only if there exists a negative cycle
        return None
    else: return dist

N, M = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = -c
V = list(range(N))
s = 0 # initial vertex
dist = bellman_ford(V, E, s)
if dist is None:
    print('inf')
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
gra = [[]for i in range(N)]
p = [[0]+[-float("inf")]*(N-1) for i in range(N+2)]
p[0][0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    gra[a-1].append([b-1,c])
for i in range(N+1):
    for j in range(N):
        for b,c in gra[j]:
            p[i+1][b] = max(p[i+1][b],p[i][j]+c,p[i][b])
print(["inf",p[N][-1]][p[N] == p[-1]])

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0

abc.sort(key=itemgetter(1))

inff = False
g_e = []
for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

for abci in abc:
    if abci[1] == N:
        g_e.append(abci[0])    

for abci in abc:
    if abci[1] in g_e and abci[0] == N:
        inff = True      

print(dist[-1]) if not inff else print("inf")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0
abc.sort()
inff = False
g_e = []
while  INF in dist:
    for abci in abc:
        if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
            dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

for abci in abc:
    if abci[1] == N:
        g_e.append(abci[0])    

for abci in abc:
    if abci[1] in g_e and abci[0] == N:
        inff = True      

print(dist[-1]) if not inff else print("inf")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0

inff = False
g_e = []

for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
        dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

for abci in abc:
    if abci[1] == N:
        g_e.append(abci[0])    

for abci in abc:
    if abci[1] in g_e and abci[0] == N:
        inff = True      

print(dist[-1]) if not inff else print("inf")

Submission status: Wrong Answer

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))
graph[1].append((0, 0))

rec = set()


@lru_cache(maxsize=None)
def solve(n):
    # n から 0 までの最長距離
    if n == 0:
        return 0
    if n in rec:
        return -INF
    ret = -INF
    rec.add(n)
    for prev, c in graph[n]:
        ret = max(ret, solve(prev) + c)
    rec.remove(n)
    return ret


ans = solve(N)
if ans != -INF:
    print(ans)
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))
graph[1].append((0, 0))

rec = set()


@lru_cache(maxsize=None)
def solve(n):
    # n から 0 までの最長距離
    if n == 0:
        return 0
    if n in rec:
        return INF
    ret = -INF
    rec.add(n)
    for prev, c in graph[n]:
        ret = max(ret, solve(prev) + c)
    rec.remove(n)
    return ret


print(solve(N))

Submission status: Wrong Answer

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))


@lru_cache(maxsize=None)
def solve(n):
    # 1 から n までの最長距離
    ret = -INF
    for prev, c in graph[n]:
        ret = max(ret, solve(prev) + c)
    if n == 1:
        return 0
    return ret


try:
    print(solve(N))
except:
    print('inf')

Submission status: Wrong Answer

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(N + 1)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))


@lru_cache(maxsize=None)
def solve(n):
    # 1 から n までの最長距離
    ret = -INF
    for prev, c in graph[n]:
        ret = max(ret, solve(prev) + c)
    if n == 1:
        return 0
    return ret


try:
    print(solve(N))
except:
    print('inf')

Submission status: Wrong Answer

Solution code:
INF = float('inf')
#vは頂点数、eは辺数
#s番目の頂点から各頂点への最短距離を求める
def Bellmanford(n, e, s):
  d = [INF]*n
  d[s] = 0
  for i in range(n):
    for e_from, e_to, e_cost in e:
      if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
        d[e_to] = d[e_from] + e_cost
        if i == n-1:
          return 'inf'
  return -d[n-1]

n,m = (int(x) for x in input().split())
edges = [None] * m

for i in range(m):
    ai, bi, ci = map(int, input().split())
    edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(n, edges, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
#vは頂点数、eは辺数
#s番目の頂点から各頂点への最短距離を求める
def Bellmanford(n, e, s):
  d = [INF]*n
  d[s] = 0
  for i in range(n):
    print(i)
    for e_from, e_to, e_cost in e:
      if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
        d[e_to] = d[e_from] + e_cost
        if i == n-1 :
          return 'inf'
  return -d[n-1]

n,m = (int(x) for x in input().split())
edges = [None] * m

for i in range(m):
    ai, bi, ci = map(int, input().split())
    edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(n, edges, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
#vは頂点数、eは辺数
#s番目の頂点から各頂点への最短距離を求める
def Bellmanford(n, e, s):
  d = [INF]*n
  d[s] = 0
  for i in range(n):
    print(i)
    for e_from, e_to, e_cost in e:
      if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
        print("aaa")
        d[e_to] = d[e_from] + e_cost
        if i == n-1:
          return 'inf'
  return -d[n-1]

n,m = (int(x) for x in input().split())
edges = [None] * m

for i in range(m):
    ai, bi, ci = map(int, input().split())
    edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(n, edges, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
graph = [float("INF") for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(n):
  flag = False
  for e in edge:
    a, b, c = e
    a, b, c = a-1, b-1, -c
    if graph[b] > graph[a]+c:
      flag = True
      graph[b] = graph[a]+c
if flag:
  print("inf")
else:
  print(-graph[n-1])

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########
class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if edge.from_edge != INF and dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1:
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)
# print(dist)
if flag:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########
class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    N = len(edges)
    d = [INF] * node_num
    d[start] = 0
    flag = False
    for i in range(N):
        update_flag = False
        for j in range(N):
            edge = edges[j]
            if edge.from_edge != INF and d[edge.to_edge] > d[edge.from_edge] + edge.cost:
                d[edge.to_edge] = d[edge.from_edge] + edge.cost
                update_flag = True
                if i == N-1:
                    flag = True
        if not update_flag:
            break
    return d, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)
if flag:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:
import collections
import sys
sys.setrecursionlimit(100000)

stack = collections.deque()
N, M = [int(ele) for ele in input().split()]
edges = []
adj_list = []
for _ in range(N+1):
    adj_list.append([])

d = [-1000000000000000000000000000000000000000000000000000000] * (N+1)

for _ in range(M):
    src, dst, w = [int(ele) for ele in input().split()]
    if src == 1:
        d[dst] = w
    edges.append([src, dst, w])
    adj_list[src].append(dst)

yet = [ele for ele in range(1, N+1)]
queue = collections.deque()


def main():
    global edges
    queue.append(1)
    bfs(queue)
    edges = list(filter(lambda x: x[0] not in yet or x[1] not in yet, edges))

    print(d[-1] if bellman_ford() != -1 else "inf")


def bfs(queue):
    if not queue:  # queueが空ならfalseで終了
        return

    n = queue[-1]
    yet.remove(n)

    for dst in adj_list[n]:
        if dst in yet and dst not in queue:  # 未訪問かつqueueにもない
            queue.appendleft(dst)
    else:
        queue.pop()
        bfs(queue)


def bellman_ford():
    for _ in range(N - 1):
        for src, dst, w in edges:
            if d[dst] < w + d[src]:
                d[dst] = w + d[src]

    for src, dst, w in edges:
        if d[dst] < w + d[src]:
            return -1

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:

N, M = [int(ele) for ele in input().split()]
edges = []
d = [-1000000000000000000000000000000000000000000000000000000] * (N+1)

for _ in range(M):
    src, dst, w = [int(ele) for ele in input().split()]
    if src == 1:
        d[dst] = w
    edges.append([src, dst, w])


def main():
    print(d[-1] if bellman_ford() != -1 else "inf")


def bellman_ford():
    for _ in range(N - 1):
        for src, dst, w in edges:
            if d[dst] < w + d[src]:
                d[dst] = w + d[src]

    for src, dst, w in edges:
        if d[dst] < w + d[src]:
            return -1

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-1:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N+1):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N-1):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-2:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    for i in range(N):
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if from_ in minus_cycle:
                minus_cycle.add(to)
            if node_to < node[to]:
                minus_cycle.add(from_)
                minus_cycle.add(to)
                node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N-1):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-2:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-1:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        else:
            exist_minus_cycle = True
            
    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()