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:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop

def solve(n, m, edges):
  nodes = [-1*math.inf] * n
  nodes[0] = 0
  for i in range(n):
    for edge in edges:
      a, b, c = edge
      if nodes[b-1] < nodes[a-1] + c:
        nodes[b-1] = nodes[a-1] + c
        if i == n-1:
          return 'inf'
  return nodes[-1]

  

def main():
  n, m = map(int, input().split(' '))
  edges = []
  for _ in range(m):
    edges.append(list(map(int, input().split(' '))))
  ans = solve(n, m, edges)
  print(ans)
  

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int, input().split())
abc = [[] for _ in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    abc[a-1].append((b-1,c))
    
S = [-float("inf")]*N
S[0] = 0
T = [0]
m = 0
while T:
    t = T.pop(0)
    m += 1
    for tb,tc in abc[t]:
        if S[tb] < S[t]+tc:
            S[tb] = S[t]+tc
            T.append(tb)
    if m > M+10000:
        print("inf")
        sys.exit()

print(S[-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M = map(int, input().split())
abc = [[] for _ in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    abc[a-1].append((b-1,c))
    
S = [-float("inf")]*N
S[0] = 0
T = [0]
m = 0
while T:
    t = T.pop(0)
    m += 1
    for tb,tc in abc[t]:
        if S[tb] < S[t]+tc:
            S[tb] = S[t]+tc
            T.append(tb)
    if m > M+1:
        print("inf")
        sys.exit()

print(S[-1])

Submission status: Wrong Answer

Solution code:
def cin():  return list(map(int,input().split()))

def bellman_ford(s):
    d = [float('inf')] * N
    d[s] = 0
    for i in range(N):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:  break
    return d

N, M = cin()
G = []
bfr = []
for i in range(M):
    s, t, w = cin()
    G.append((s - 1, t - 1, -w))
    if t == N:  bfr.append([s - 1, w])

flg = 0
for node in bfr:
    res = -bellman_ford(N - 1)[node[0]]
    if res + node[1] > 0:  flg = 1
if flg:  print("inf")
else:
    res = bellman_ford(0)
    ans = -res[N - 1]
    print(ans)

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, origin, to, cost):
        self.origin = origin
        self.to = to
        self.cost = cost

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

edges = [None] * M

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

#コストを最小化するような問題として読み替える

dist = [float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != float("inf") and dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    i += 1

    if not isUpdated:
        break

    if i == N-1:
        break

print(dist)

#最短経路探索が終了
#負のサイクルを検知する
isUpdated = [False for _ in range(N)]
for i in range(N):
    for e in edges:
        if dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated[e.to] = True


if isUpdated[N-1]:
    print("inf")

else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []
minC = float("inf")
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a-1, b-1, c))
    minC = min(minC, c)

dist = [-abs(N * minC) for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -abs(N*minC) and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == M+1:
        break

if i == M+1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != float("inf") and dist[e.to] > dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == M+1:
        break

if i == M+1:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-10**18 for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*10**18 and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == M+1:
        break

if i == M+1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == M+1:
        break

if i == M+1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == M:
        break

if i == M:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == N:
        break

if i == N:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    # print(dist)
    i += 1

    if not isUpdated:
        break

    if i == N-1:
        break

if i == N-1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:
    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    i += 1

    if not isUpdated:
        break

    if i == N:
        break

if i == N-1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
class Edge:

    def __init__(self, f, to, cost):
        self.to = to
        self.origin = f
        self.cost = cost

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

edges = []

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

dist = [-1*float("inf") for _ in range(N)]
dist[0] = 0
i = 0
while True:
    isUpdated = False
    for e in edges:
        if dist[e.origin] != -1*float("inf") and dist[e.to] < dist[e.origin] + e.cost:
            dist[e.to] = dist[e.origin] + e.cost
            isUpdated = True
    i += 1

    if not isUpdated:
        break

    if i == N-1:
        break

if i == N-1:
    print("inf")
else:
    print(dist[N-1])

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-(10 ** 9 * 2000)] * n

# Bellman-Ford
v[0] = 0
for i in range(n):
    tmp = v[-1]
    for a, b, cost in e:
        if v[a-1] + cost > v[b-1]:
            v[b-1] = v[a-1] + cost
    if tmp != v[-1]: break        
else:
    print(v[n-1])
    exit()

print("inf")

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-(10 ** 9 * 20000)] * n

# Bellman-Ford
v[0] = 0
for i in range(n):
    flag = False
    for a, b, cost in e:
        if v[a-1] + cost > v[b-1]:
            v[b-1] = v[a-1] + cost
            flag = True
    if not flag: break        
else:
    #負の閉路が存在する
    print("inf")
    exit()

print(v[n-1])

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-10 ** 9 * 2000] * n

# Bellman-Ford
v[0] = 0
for i in range(n):
    flag = False
    for a, b, cost in e:
        if v[a-1] + cost > v[b-1]:
            v[b-1] = v[a-1] + cost
            flag = True
    if not flag: break        
else:
    #負の閉路が存在する
    print("inf")
    exit()

print(v[n-1])

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [10 ** 9 * 2000] * n

# 辺のコストを-1倍
for i in range(m):
    e[i][2] *= -1

# Bellman-Ford
v[0] = 0
for i in range(n):
    flag = False
    for a, b, cost in e:
        if v[a-1] + cost < v[b-1]:
            v[b-1] = v[a-1] + cost
            flag = True
    if not flag: break        
else:
    #負の閉路が存在する
    print("inf")
    exit()

print(v[n-1] * -1)

Submission status: Wrong Answer

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

G = [[] for _ in range(N)]

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

INF = 10**15
D = [INF] * N
D[0] = 0
for now in range(N):
  for nxt, dist in G[now]:
    if D[nxt] > D[now] + dist:
      D[nxt] = D[now] + dist

NEG = [False] * N
for now in range(N):
  for nxt, dist in G[now]:
    if D[nxt] > D[now] + dist:
      D[nxt] = D[now] + dist
      NEG[nxt] = True
    if NEG[now] == True:
      NEG[nxt] = True
      
if NEG[-1] == True:
  print("inf")
else:
  print(-D[-1])

Submission status: Wrong Answer

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n:
        #正のループがある
        print(float("INF"))
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split()) 
G=[] ; Y=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])

# den=set([])
# for i  in range(m):
#     if uf.same(0,Y[i][0]): 
#         G.append(Y[i])
#         den.add(Y[i][0]);den.add(Y[i][1])
# now=len(den)

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(2*n+3):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                if i==2*n+2 : print("inf");exit()

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split()) 
G=[] ; Y=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])

# den=set([])
# for i  in range(m):
#     if uf.same(0,Y[i][0]): 
#         G.append(Y[i])
#         den.add(Y[i][0]);den.add(Y[i][1])
# now=len(den)

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(n+3):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                if i==n+2 : print("inf");exit()

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())



n,m=map(int,input().split()) ; uf=UnionFind(n)
G=[] ; Y=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    Y.append([a,b,-w])
    uf.union(a,b)

den=set([])
for i  in range(m):
    if uf.same(0,Y[i][0]): 
        G.append(Y[i])
        den.add(Y[i][0]);den.add(Y[i][1])
now=len(den)

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(now):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                if i==now-1 : print("inf");exit()

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
G=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])
    G1[a].append(b)

# サイクル検出　
# 頂点v から出発した探索が、v から行ける全頂点の探索を終える前に(帰りがけ状態になる前に)v に戻ってきてしまう
# seen[v]==True and finished[v]==False のときにdfs(v)をしようとしたらOUT

from collections import deque
# class CYCLE:
#     def __init__(self,arr):
#         self.G=arr
#         self.seen=[0]*n  #行きがけでv が訪問済みか
#         self.finished=[0]*n #帰りがけでv が訪問済み
#         self.cycle=[]
#         self.pos =-1 # サイクル中に含まれる頂点
#         self.hist= deque([]) # 訪問履歴
# 
#     def dfs(self,x,p):
#         self.seen[x]=True
#         self.hist.append(x)
#         for v in self.G[x]:
#             #if v==p:continue
#             if self.finished[v]:continue 
#             if self.seen[v] and self.finished[v]==0:
#                 self.pos=v; return
#             self.dfs(v,x)
#             if self.pos!=-1: return
#         self.hist.pop()
#         self.finished[x]=True
# 
#     def judge(self): # サイクルがあるかどうかだけ判定したい
#         self.dfs(0,-1)
#         if self.pos==-1: return 0
#         else: return 1
# 
#     def maru(self): # サイクルの成分もほしい
#         self.dfs(0,-1)
#         while self.hist:
#             t= self.hist.pop()
#             self.cycle.append(t)
#             if t==self.pos: break
#         return self.cycle
# cy=CYCLE(G1)
# # print(cy.maru())
# if cy.judge():
#     print("inf");exit()

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(m):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                if i==m-1 : print("inf");exit()

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
G=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])
    G1[a].append(b)

# サイクル検出　
# 頂点v から出発した探索が、v から行ける全頂点の探索を終える前に(帰りがけ状態になる前に)v に戻ってきてしまう
# seen[v]==True and finished[v]==False のときにdfs(v)をしようとしたらOUT

from collections import deque
# class CYCLE:
#     def __init__(self,arr):
#         self.G=arr
#         self.seen=[0]*n  #行きがけでv が訪問済みか
#         self.finished=[0]*n #帰りがけでv が訪問済み
#         self.cycle=[]
#         self.pos =-1 # サイクル中に含まれる頂点
#         self.hist= deque([]) # 訪問履歴
# 
#     def dfs(self,x,p):
#         self.seen[x]=True
#         self.hist.append(x)
#         for v in self.G[x]:
#             #if v==p:continue
#             if self.finished[v]:continue 
#             if self.seen[v] and self.finished[v]==0:
#                 self.pos=v; return
#             self.dfs(v,x)
#             if self.pos!=-1: return
#         self.hist.pop()
#         self.finished[x]=True
# 
#     def judge(self): # サイクルがあるかどうかだけ判定したい
#         self.dfs(0,-1)
#         if self.pos==-1: return 0
#         else: return 1
# 
#     def maru(self): # サイクルの成分もほしい
#         self.dfs(0,-1)
#         while self.hist:
#             t= self.hist.pop()
#             self.cycle.append(t)
#             if t==self.pos: break
#         return self.cycle
# cy=CYCLE(G1)
# # print(cy.maru())
# if cy.judge():
#     print("inf");exit()

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(n):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                if i==n-1 : print("inf");exit()

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
print("inf")

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
G=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,-w])
    G1[a].append(b)

# サイクル検出　
# 頂点v から出発した探索が、v から行ける全頂点の探索を終える前に(帰りがけ状態になる前に)v に戻ってきてしまう
# seen[v]==True and finished[v]==False のときにdfs(v)をしようとしたらOUT

from collections import deque
class CYCLE:
    def __init__(self,arr):
        self.G=arr
        self.seen=[0]*n  #行きがけでv が訪問済みか
        self.finished=[0]*n #帰りがけでv が訪問済み
        self.cycle=[]
        self.pos =-1 # サイクル中に含まれる頂点
        self.hist= deque([]) # 訪問履歴
        
    def dfs(self,x,p):
        self.seen[x]=True
        self.hist.append(x)
        for v in self.G[x]:
            #if v==p:continue
            if self.finished[v]:continue 
            if self.seen[v] and self.finished[v]==0:
                self.pos=v; return
            self.dfs(v,x)
            if self.pos!=-1: return
        self.hist.pop()
        self.finished[x]=True
        
    def judge(self): # サイクルがあるかどうかだけ判定したい
        self.dfs(0,-1)
        if self.pos==-1: return 0
        else: return 1
        
    def maru(self): # サイクルの成分もほしい
        self.dfs(0,-1)
        while self.hist:
            t= self.hist.pop()
            self.cycle.append(t)
            if t==self.pos: break
        return self.cycle
cy=CYCLE(G1)
# print(cy.maru())
if cy.judge():
    print("inf");exit()

def Bellman(s):
    ansdist=[inf for i in range(n)]
    ansdist[s]=0
    for i in range(n):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] > ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                # if i==n-1 : return -1

    return ansdist

print(-Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())
G=[]
G1=[[] for i in range(n)]
for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1
    G.append([a,b,w])
    G1[a].append(b)

# サイクル検出　
# 頂点v から出発した探索が、v から行ける全頂点の探索を終える前に(帰りがけ状態になる前に)v に戻ってきてしまう
# seen[v]==True and finished[v]==False のときにdfs(v)をしようとしたらOUT

from collections import deque
class CYCLE:
    def __init__(self,arr):
        self.G=arr
        self.seen=[0]*n  #行きがけでv が訪問済みか
        self.finished=[0]*n #帰りがけでv が訪問済み
        self.cycle=[]
        self.pos =-1 # サイクル中に含まれる頂点
        self.hist= deque([]) # 訪問履歴
        
    def dfs(self,x,p):
        self.seen[x]=True
        self.hist.append(x)
        for v in self.G[x]:
            #if v==p:continue
            if self.finished[v]:continue 
            if self.seen[v] and self.finished[v]==0:
                self.pos=v; return
            self.dfs(v,x)
            if self.pos!=-1: return
        self.hist.pop()
        self.finished[x]=True
        
    def judge(self): # サイクルがあるかどうかだけ判定したい
        self.dfs(0,-1)
        if self.pos==-1: return 0
        else: return 1
        
    def maru(self): # サイクルの成分もほしい
        self.dfs(0,-1)
        while self.hist:
            t= self.hist.pop()
            self.cycle.append(t)
            if t==self.pos: break
        return self.cycle
cy=CYCLE(G1)
# print(cy.maru())
if cy.judge():
    print("inf");exit()

def Bellman(s):
    ansdist=[-10**15 for i in range(n)]
    ansdist[s]=0
    for i in range(n):
        for edge in G:
            a,b,d=edge
            #辺ごとに見ていき、infでない(到達済み)頂点から伸びた辺であり、最小値を更新できるようなら緩和する
            if ansdist[b] < ansdist[a]+d:  #inf>inf はFalse
                ansdist[b]= ansdist[a]+d
                #if i==n-1 : return -1

    return ansdist

print(Bellman(0)[-1])

Submission status: Wrong Answer

Solution code:
def moores_d(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    stack = [s]
    for _ in range(n):
        next_stack = []
        while stack:
            vf = stack.pop()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    next_stack.append(vt)
        stack = next_stack
        if not stack:
            break
    if stack: #閉路の存在
        stack = list(range(n))
        minus_inf = -float('inf')
        next_stack = []
        for vf in stack:
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = minus_inf
                    next_stack.append(vt)
        stack = next_stack
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = moores_d(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')