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, deque

def exist_closed_route(graph, start_node):
  queue = deque()
  queue.append([start_node, 0])
  done = []
  
  while len(queue) > 0:
    prv_node, node_num = queue.popleft()
    for node, dis in graph[prv_node]:
      if node == start_node:
        if node_num == 0 and graph[node] + graph[prv_node] < 0:
          continue
        else:
          return True
      if node not in done:
        queue.append([node,node_num+1])
        done.append(node)
  return False 

def get_max_score(graph, n):
  costs = [0] + [-1*float('inf') for _ in range(n-1)]
  flgs = [False for _ in range(n)]
  
  queue = deque()
  while (not all(flgs)):
    tmp_max = -1 * float('inf')
    idx = 0
    for cost, flg in zip(costs, flgs):
      if flg is False and tmp_max < cost:
        tmp_max = cost
        tmp_idx = idx
      idx += 1
    queue.append(tmp_idx)
    flgs[tmp_idx] = True
    
    prv_node = queue.popleft()
    for node, dis in graph[prv_node]:
      if costs[node] < dis + costs[prv_node]:
        costs[node] = dis + costs[prv_node]

  return costs[-1]

n, m = map(int, input().split())
graph = defaultdict(list)

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

#閉路があったらinf  
for i in range(n):
  if exist_closed_route(graph, i) is True:
    print('inf')
    exit()

#スコアの最大値を算出
print(get_max_score(graph, n))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

def exist_closed_route(graph, start_node):
  queue = deque()
  queue.append(start_node)
  done = []
  
  while len(queue) > 0:
    prv_node = queue.popleft()
    for node, dis in graph[prv_node]:
      if node == start_node:return True
      if node not in done:
        queue.append(node)
        done.append(node)
  return False 

def get_max_score(graph, n):
  costs = [0] + [-1*float('inf') for _ in range(n-1)]
  flgs = [False for _ in range(n)]
  
  queue = deque()
  while (not all(flgs)):
    tmp_max = -1 * float('inf')
    idx = 0
    for cost, flg in zip(costs, flgs):
      if flg is False and tmp_max < cost:
        tmp_max = cost
        tmp_idx = idx
      idx += 1
    queue.append(tmp_idx)
    flgs[tmp_idx] = True
    
    prv_node = queue.popleft()
    for node, dis in graph[prv_node]:
      if costs[node] < dis + costs[prv_node]:
        costs[node] = dis + costs[prv_node]

  return costs[-1]

n, m = map(int, input().split())
graph = defaultdict(list)

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

#閉路があったらinf  
for i in range(n):
  if exist_closed_route(graph, i) is True:
    print('inf')
    exit()

#スコアの最大値を算出
print(get_max_score(graph, n))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    _INF = - int(1e15)
    abc = [list(map(int, input().split())) for i in range(M)]

    print("inf")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    _INF = - int(1e15)
    score = [_INF] * (N + 1)
    abc = [list(map(int, input().split())) for i in range(M)]

    score[1] = 0
    count = 0
    while True:
        no_change = True
        for j in range(M):
            a, b, c = abc[j]
            if score[a] != _INF:
                if score[b] < score[a] + c:
                    score[b] = score[a] + c
                    no_change = False
        if no_change:
            print(score[N])
            break
        count += 1
        if count > N:
            print("inf")
            break
    # print(score)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for i in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
            if i==v-1 and b==v-1:
                return -1
        # 更新が無ければbreak
        if not f:
            break

    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a-1,b-1,-c))

ans=bellman_ford(n,0,e)
if ans==-1:
    print("inf")
else:
    print(-ans[-1])

Submission status: Wrong Answer

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

n,m=map(int,input().split())
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a-1,b-1,-c))
ans=BellmanFord(e,n,0)
if ans==-1:
    print("inf")
else:
    print(-ans[-2])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:break
    else:
        # V回目まで更新があったら負の閉路がある
        return -1
    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a-1,b-1,-c))

ans=bellman_ford(n,0,e)
if ans==-1:
    print("inf")
else:
    print(-ans[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a].append([b,c])

from collections import deque
q=deque([1])
g=[-10**100 for i in range(n+1)]
g[1]=0
ct=0
while q:
    p=q.popleft()
    ll=l[p]
    for i,j in ll:
        g[i]=max(g[i],g[p]+j)
        q.append(i)
    ct+=1
    if ct==n:
        tmp=g[n]
    if ct==2*n:
        if tmp!=g[n]:
            print("inf")
        exit()

print(g[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * (v+1)
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:break
    else:
        # V回目まで更新があったら負の閉路がある
        return -1
    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a,b,-c))

ans=bellman_ford(n,1,e)
if ans==-1:
    print("inf")
else:
    print(-ans[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:break
    else:
        # V回目まで更新があったら負の閉路がある
        return -1
    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a,b,-c))

ans=bellman_ford(n+1,1,e)
if ans==-1:
    print("inf")
else:
    print(-ans[n])

Submission status: Wrong Answer

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == M:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC061D - Score Attack
def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for _ in range(N - 1):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w

    # detect negative cycles
    for v, u, w in E:
        if dist[v] != INF and dist[v] - w != dist[u]:
            return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC061D - Score Attack
def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for _ in range(N - 1):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w

    # detect negative cycles
    for v, u, w in E:
        if dist[v] != INF and dist[v] - w < dist[u]:
            return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for _ in range(M - 1):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w

    # detect negative cycles
    for v, u, w in E:
        if dist[v] != INF and dist[v] - w < dist[u]:
            return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    # ベルマンフォード法で負の最短経路(スコアの最大値)を導出
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in ABC:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Wrong Answer

Solution code:
def func(n, q, mode):
    global ans
    
    for i in range(n):
        q_next = []
        for r, c, c_ in q:
            if not mode:
                cost[r] = max(cost[r], c+c_)
            else:
                if c+c_ > cost[r]:
                    ans = 'inf'
                    return   
            q_next.extend([(r_,c+c_,x) for r_, x in graph[r]])
        q = q_next[:]
    
N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}
cost = [-10**20] * (N+1)
ans = None

for i in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
cost[1] = 0
q = [(r, c, 0) for r, c in graph[1]]

func(N-1, q, 0)
ans = cost[N]
func(N, q, 1)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    if a <= c <= b:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    n, m = LI()
    e = defaultdict(int)
    for i in range(1, n + 1): e[i] = 0
    for i in range(m):
        a, b = LI()
        e[a] += 1
        e[b] += 1
    for i in e.values():
        print(i)
    return

#C
def C():
    n, k = LI()
    d = defaultdict(int)
    for i in range(1, 10**5+1): d[i] = 0
    for i in range(n):
        a, b = LI()
        d[a] += b
    for key, valus in d.items():
        k -= valus
        if k <= 0:
            print(key)
            return
    return

#D
def D():
    n, m = LI()
    edg = defaultdict(list)
    r_edg = defaultdict(list)
    for _ in range(m):
        a, b, c = LI_()
        edg[a].append((b, c + 1))
        r_edg[b].append(a)
    q = deque()
    q.append(n-1)
    check = [True] * n
    check[n-1] = False
    while q:
        now = q.pop()
        for e in r_edg[now]:
            if check[e]:
                check[e] = False
                q.appendleft(e)
    def dfs(v, score):
        res = False
        for e, c in edg[v]:
            if e == i and score > 0:
                return True
            if close[e]:
                close[e] = False
                res |= dfs(e, score + c)
                close[e] = True
        return res
    for i in range(n):
        if check[i]:
            continue
        close = [True] * n
        if dfs(i, 0):
            print("inf")
            return
    def dfsans(v, score):
        res = -inf
        for e, c in edg[v]:
            if e == n - 1:
                res = max(res, score + c)
                continue
            if not check[e] and close[e]:
                close[e] = False
                res = max(res, dfsans(e, score + c))
                close[e] = True
        return res
    close = [True] * n
    print(dfsans(0, 0))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    if a <= c <= b:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    n, m = LI()
    e = defaultdict(int)
    for i in range(1, n + 1): e[i] = 0
    for i in range(m):
        a, b = LI()
        e[a] += 1
        e[b] += 1
    for i in e.values():
        print(i)
    return

#C
def C():
    n, k = LI()
    d = defaultdict(int)
    for i in range(1, 10**5+1): d[i] = 0
    for i in range(n):
        a, b = LI()
        d[a] += b
    for key, valus in d.items():
        k -= valus
        if k <= 0:
            print(key)
            return
    return

#D
def D():
    n, m = LI()
    edg = defaultdict(list)
    r_edg = defaultdict(list)
    for _ in range(m):
        a, b, c = LI_()
        edg[a].append((b, c + 1))
        r_edg[b].append(a)
    q = deque()
    q.append(n-1)
    check = [True] * n
    check[n-1] = False
    while q:
        now = q.pop()
        for e in r_edg[now]:
            if check[e]:
                check[e] = False
                q.appendleft(e)
    def dfs(v, score):
        res = False
        for e, c in edg[v]:
            if e == i and score > 0:
                return True
            if close[e]:
                close[e] = False
                res |= dfs(e, score + c)
                close[e] = True
        return res
    for i in range(n):
        if check[i]:
            continue
        close = [True] * n
        if dfs(i, 0):
            print("inf")
            return
    def dfsans(v, score):
        res = -inf
        for e, c in edg[v]:
            if e == n - 1:
                res = max(res, score + c)
                continue
            if check[e]:
                check[e] = False
                res = max(res, dfsans(e, score + c))
                check[e] = True
        return res
    check = [True] * n
    print(dfsans(0, 0))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())

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

    INF = int(1E18)

    D = [INF for _ in range(N)]
    D[0] = 0

    loop = False
    for c in range(2*N):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                D[j] = D[i] + d
                update = True
        if not update:
            break
        if c == N-1:
            loop = True
            break
    if loop:
        print('inf')
    else:
        print(-D[N-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())

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

    INF = int(1E18)

    D = [INF for _ in range(N)]
    D[0] = 0

    loop = False
    for c in range(2*N):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                D[j] = D[i] + d
                update = True
        if not update:
            break
        if c > N:
            loop = True
            break
    if loop:
        print('inf')
    else:
        print(-D[N-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())

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

    INF = int(1E18)

    D = [INF for _ in range(N)]
    D[0] = 0

    loop = False
    for c in range(2*N):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                D[j] = D[i] + d
                update = True
        if not update:
            break
        if c > N-1:
            loop = True
            break
    if loop:
        print('inf')
    else:
        print(-D[N-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def BellmanFord(g: Graph, s):
    """ベルマンフォード法によって最短経路を求める
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    # 辺の緩和
    for i in range(N):
        for from_ in range(N):      # ここの２重ループはO(M)
            for to_, weight in g.E[from_]:
                if dist[from_] != INF and dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
                    if i == N-1:
                        return None, None
    # # 負の重みの閉路がないかチェック
    # for from_ in range(N):
    #     for to_, weight in g.E[from_]:
    #         if dist[from_]+weight < dist[to_]:
    #             return None, None

    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for f, t, w in zip(a, b, c):
        g.add_edge([f-1, t-1, -w])

    dist, prev = BellmanFord(g, 0)

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def BellmanFord(g: Graph, s):
    """ベルマンフォード法によって最短経路を求める
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    # 辺の緩和
    for _ in range(N-1):
        for from_ in range(N):      # ここの２重ループはO(M)
            for to_, weight in g.E[from_]:
                if dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
    # 負の重みの閉路がないかチェック
    for from_ in range(N):
        for to_, weight in g.E[from_]:
            if dist[from_]+weight < dist[to_]:
                return None, None

    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for f, t, w in zip(a, b, c):
        g.add_edge([f-1, t-1, -w])

    dist, prev = BellmanFord(g, 0)

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist

N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b,c = map(int,input().split())
    ABC.append([a,b,-c])
    
Dist = BellmanFord(ABC,N,1)
if Dist == -1:
    print("inf")
else:
    print(-Dist[-1])

Submission status: Wrong Answer

Solution code:
#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v+1):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist

N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b,c = map(int,input().split())
    ABC.append([a,b,-c])
    
Dist = BellmanFord(ABC,N,1)
if Dist == -1:
    print("inf")
else:
    print(-Dist[-1])

Submission status: Wrong Answer

Solution code:
#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist

N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b,c = map(int,input().split())
    ABC.append([a,b,-c])
    
Dist = BellmanFord(ABC,N,1)
if Dist == -1:
    print("inf")
else:
    print(-Dist[-1])

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
try:print(-int(csgraph.bellman_ford(csr_matrix(([-c for c in t[3::3]],(t[1::3],t[2::3])),[n+1]*2),1,[1])[0,n]))
except:print('inf')

Submission status: Wrong Answer

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

d = [float('inf')] * n
d[0] = 0

for _ in range(n - 1):
    for i in range(m):
        d[b[i]] = min(d[b[i]], d[a[i]] + c[i])

for i in range(m):
    if d[a[i]] + c[i] < d[b[i]]:
        print('inf')
        exit(0)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [None]*M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a-1, b-1, c)
d = [-float("inf") for _ in range(N)]
d[0] = 0

for i in range(N):
    for e in E:
        if d[e[0]] != -float("inf") and d[e[1]] < d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                print("inf")
                exit()

print(d[-1])