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
input = sys.stdin.readline
import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

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

  try:
    d = np.array(d)
    d = shortest_path(d)
    #print(d)
    tmp = (-1*d[0][n-1])
    print(int(-1*d[0][n-1]))

  except:
    print("inf")
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
from scipy.sparse.csgraph import johnson
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = 0.001
  try:
    d = johnson(d,directed=True)
    tmp = (-1*d[0][n-1])
    print(math.ceil(-1*d[0][n-1]))

  except:
    print("inf")
solve()

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import johnson
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    if not c == 0:
      d[a-1][b-1] = c*-1
    else:
      d[a-1][b-1] = 0.001
  try:
    d = johnson(d,directed=True)
    tmp = (-1*d[0][n-1])
    print(int(-1*d[0][n-1]))

  except:
    print("inf")
solve()

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import johnson
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c*-1
  try:
    d = johnson(d,directed=True)
    tmp = str(-1*d[0][n-1])
    tmp = tmp[0:-2]
    print(tmp)
  except:
    print("inf")
solve()

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import johnson
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c*-1
  try:
    d = johnson(d,directed=True)
    #floatの誤差が怖い
    print(int(-1*d[0][n-1]))
  except:
    print("inf")
solve()

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import bellman_ford
def solve():
  n,m = (int(i) for i in input().split())
  d = [[float("inf")]*n for _ in range(n)]

  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c*-1
  try:
    d = bellman_ford(d,directed=True)
    #floatの誤差が怖い
    print(int(-1*d[0][n-1]))
  except:
    print("inf")
solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():

    class BellmanFord(object):
        """
        construct: O(VE)
        """

        def __init__(self,edges,start=0):
            """
            :param list of list of [node,cost] edges:
            :param int start=0:
            """
            self.__n=len(edges)
            self.__dist=[float("inf")]*self.__n
            self.__dist[start]=0
            self.__calculate(edges,start)

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

        def __calculate(self,edges,start): # relaxingという
            for k in range(self.__n): # n回更新する。n回目に更新が行われたら負経路あり。
                update=False
                for v in range(self.__n):
                    for u,cost in edges[v]:
                        if (self.dist[v]!=float("inf")) and (self.dist[u]>self.dist[v]+cost):
                            self.__dist[u]=self.dist[v]+cost
                            update=True
                else:
                    if (update is False): # 更新されない＝終わり
                        return
                    elif (update is True) and (k==self.__n-1): # 負の閉路検出
                        self.__dist=[-float("inf")]*self.__n

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

    # Bellman-Ford
    bel=BellmanFord(edges)
    print(-bel.dist[n-1] if bel.dist[n-1]!=-INF else 'inf')


resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():

    class BellmanFord(object):
        """
        construct: O(VE)
        """

        def __init__(self,edges,start=0):
            """
            :param list of list of [node,cost] edges:
            :param int start=0:
            """
            self.__n=len(edges)
            self.__dist=[float("inf")]*self.__n
            self.__dist[start]=0
            self.__calculate(edges,start)

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

        def __calculate(self,edges,start): # relaxingという
            for k in range(self.__n): # n回更新する。n回目に更新が行われたら負経路あり。
                update=False
                for v in range(self.__n):
                    for u,cost in edges[v]:
                        if self.dist[u]>self.dist[v]+cost:
                            self.__dist[u]=self.dist[v]+cost
                            update=True
                else:
                    if (update is False): # 更新されない＝終わり
                        return
                    elif (update is True) and (k==self.__n-1): # 負の閉路検出
                        self.__dist=[-float("inf")]*self.__n

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

    # Bellman-Ford
    bel=BellmanFord(edges)
    print(-bel.dist[n-1] if -bel.dist[n-1]!=INF else 'inf')


resolve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 10**12
dp = [-INF for _ in range(N+1)]
#edges = [[INF] * (N+1) for _ in range(N+1)]
#for _ in range(M):
#  s, g, c = map(int, input().split())
#  edges[s][g] = c
edges = []
for _ in range(M):
  s, g, c = map(int, input().split())
  edges.append((s, g, c))
dp[1] = 0
cnt = 0
while True:
  update = False
  for s, g, c in edges:
    if dp[s] != -INF and dp[g] < dp[s] + c:
      dp[g] = dp[s] + c
      update = True
  if not update:
    print(dp[N])
    break
  elif cnt >= M-1:
    print('inf')
    break
  cnt += 1

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 10**12
dp = [-INF for _ in range(N+1)]
#edges = [[INF] * (N+1) for _ in range(N+1)]
#for _ in range(M):
#  s, g, c = map(int, input().split())
#  edges[s][g] = c
edges = []
for _ in range(M):
  s, g, c = map(int, input().split())
  edges.append((s, g, c))
dp[1] = 0
cnt = 0
while True:
  update = False
  for s, g, c in edges:
    if dp[s] != -INF and dp[g] < dp[s] + c:
      dp[g] = dp[s] + c
      update = True
  if not update:
    print(dp[N])
    break
  elif cnt >= M:
    print('inf')
    break
  cnt += 1

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    INF = 1e20
    cost = [INF] * N
    cost[0] = 0

    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        edges.append((a-1, b-1, -c))
    
    fin = False
    count = 0
    while True:
        no_change = True
        for i in range(M):
            a, b, c = edges[i]
            if cost[a] + c < cost[b]:
                cost[b] = cost[a] + c
                no_change = False
        count += 1
        if no_change:
            fin = True
            break
        if count > 2 * N:
            break
    
    if fin:
        print(-int(cost[N-1]))
    else:
        print("inf")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    INF = int(1e20)
    cost = [INF] * N
    cost[0] = 0

    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        edges.append((a-1, b-1, -c))
    
    fin = False
    count = 0
    while True:
        no_change = True
        for i in range(M):
            a, b, c = edges[i]
            if cost[a] + c < cost[b]:
                cost[b] = cost[a] + c
                no_change = False
        count += 1
        if no_change:
            fin = True
            break
        if count > N:
            break
    
    if fin:
        print(-cost[N-1])
    else:
        print("inf")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    INF = int(1e15)
    cost = [INF] * N
    cost[0] = 0

    edges = []
    for i in range(M):
        a, b, c = map(int, input().split())
        edges.append((a-1, b-1, -c))
    
    fin = False
    count = 0
    while True:
        no_change = True
        for i in range(M):
            a, b, c = edges[i]
            if cost[a] + c < cost[b]:
                cost[b] = cost[a] + c
                no_change = False
        count += 1
        if no_change:
            fin = True
            break
        if count > N:
            break
    
    if fin:
        print(-cost[N-1])
    else:
        print("inf")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#ベルマンフォード法
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m=map(int,input().split())
edge=np.array([input().split() for _ in range(m)],dtype=np.int64).T
graph=csr_matrix(((-edge[2],edge[:2]-1)),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=[0])[0].astype(int)
        print(-ans[-1])
        break
    except:
        #負経路の場合
        print("inf")
        break

Submission status: Wrong Answer

Solution code:
#ベルマンフォード法
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m=map(int,input().split())
edge=np.array([input().split() for _ in range(m)],dtype=np.int64).T
graph=csr_matrix(((-edge[2],edge[:2]-1)),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=0)
        print(-int(ans[n-1]))
        break
    except:
        #負経路の場合
        print("inf")
        break

Submission status: Wrong Answer

Solution code:
def calc_score(edges, num_v):
  inf = float("inf")
  score = [inf for _ in range(num_v+1)]
  score[1] = 0
  
  # 辺の緩和
  for i in range(num_v):
    for a, b, w in edges:
      if score[b] > score[a] - w:
        score[b] = score[a] - w
        if i == num_v-1:
          return None
  return score[-1]

def solve(): 
  ans = calc_score(edges, N)
  flg = ans is not None
  print(-ans if flg else "inf")


if __name__ == "__main__":
  import sys
  input = sys.stdin.readline
  N, M = tuple(map(int, input().split()))
  edges = [list(map(int, input().split())) for _ in range(M)]
  solve()

Submission status: Wrong Answer

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

P = [0.1] * (n+1)
P[1] = 0
F = [[0] * 2 for i in range(n+1)]
F[1][0] = 1
F[n][1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans0 = P[:]


for i in range(1):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans1 = P[:]

#print(F)

def d():
    for i in range(n+1):
        if F[i] == [1, 1] and ans1[i] > ans0[i]:
            return "inf"
    return ans0[n]

print(d())

Submission status: Wrong Answer

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

P = [0.1] * (n+1)
P[1] = 0
F = [0] * (n+1)
F[1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]] == 1 :
            F[A[j][1]] = 1
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans0 = P[:]


for i in range(n):
    for j in range(m):
        if F[A[j][0]] == 1 :
            F[A[j][1]] = 1
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans1 = P[:]

def d():
    for i in range(n+1):
        if F[i] == 1 and ans1[i] > ans0[i]:
            return "inf"
    return ans0[n]

print(d())

Submission status: Wrong Answer

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

P = [0.1] * (n+1)
P[1] = 0

for i in range(n):
    for j in range(m):
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans0 = P[n]


for i in range(n):
    for j in range(m):
        if P[A[j][1]] == 0.1 and P[A[j][0]] != 0.1:
            P[A[j][1]] = P[A[j][0]] + A[j][2]
        else:
            #print((P[A[j][1]], P[A[j][0]] + A[j][2]))
            P[A[j][1]] = max(P[A[j][1]], P[A[j][0]] + A[j][2])
            #print(P[A[j][1]])

ans1 = P[n]

if ans0 != ans1:
    print("inf")
else:
    print(ans0)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 10**12
edges = [tuple(map(int, input().split())) for _ in range(M)]
dp = [-INF] * (N+1)
cnt = 0
dp[1] = 0
while True:
  update = False
  for a, b, c in edges:
    if dp[a] != -1 and dp[b] < dp[a] + c:
      dp[b] = dp[a] + c
      update = True
      cnt += 1
  if update:
    if cnt == N:
      print('inf')
      exit()
  else:
    break
print(dp[N])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 10**12
edges = [] * (M+1)
for _ in range(M):
  a, b, c = map(int, input().split())
  edges.append((a, b, c))
dp = [-INF] * (N+1)
cnt = 0
dp[1] = 0
while True:
  update = False
  for i in range(M):
    a, b, c = edges[i]
    if dp[a] != -1 and dp[b] < dp[a] + c:
      dp[b] = dp[a] + c
      update = True
      cnt += 1
  if update:
    if cnt == N:
      print('inf')
      exit()
  else:
    break
print(dp[N])

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10


def bellman_ford(v, G):
    ret = [INF] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    for _ in range(len(G)):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = -INF

    return ret


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

ans = bellman_ford(0, G)[-1]
print('inf' if ans == -INF else -ans)

Submission status: Wrong Answer

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

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

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N-1]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    if ans == d[N-1]:
        print(-ans)
    else:
        print(-1)


main()

Submission status: Wrong Answer

Solution code:
def solve():
    global dp
    while True:
        flag = False
        for i in range(M):
            if dp[graph[i].f] + graph[i].cost > dp[graph[i].to] and dp[graph[i].f] != -float("inf"):
                dp[graph[i].to] = dp[graph[i].f] + graph[i].cost
                flag = True
        if not flag :
            break
def check_p_roop():
    d = [0 for i in range(N)]
    for i in range(N+1):
        for j in range(M):
            if d[graph[j].f] + graph[j].cost > d[graph[j].to] :
                d[graph[j].to] = d[graph[j].f] + graph[j].cost
                if i == N  :
                    return True
    return False

def main():
    global  N,M ,dp,graph
    N, M = map(int, input().split())
    dp = [-float("inf") for i in range(N)]
    dp[0] = 0
    graph = [0 for _ in range(M)]

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

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

    if check_p_roop():
        print("inf")
    else:
        solve()
        print(dp[N - 1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    global dp
    while True:
        flag = False
        for i in range(M):
            if dp[graph[i].f] + graph[i].cost > dp[graph[i].to] and dp[graph[i].f] != -float("inf"):
                dp[graph[i].to] = dp[graph[i].f] + graph[i].cost
                flag = True
        if not flag :
            break
def check_p_roop():
    d = [0 for i in range(N)]
    for i in range(N+1):
        for j in range(M):
            if d[graph[j].f] + graph[j].cost > d[graph[j].to] :
                d[graph[j].to] = d[graph[j].f] + graph[j].cost
                if i == N  :
                    return True
    return False


if __name__ == '__main__':
    N, M = map(int, input().split())
    dp = [-float("inf") for i in range(N)]
    dp[0] = 0
    graph = [0 for _ in range(M)]
    class Edge:
        def __init__(self, f, to, cost):
            self.f = f
            self.to = to
            self.cost = cost
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = Edge(a-1, b-1, c)

    if check_p_roop():
        print("inf")
    else :
        solve()
        print(dp[N-1])

Submission status: Wrong Answer

Solution code:
def solve():
    global dp
    while True:
        flag = False
        for i in range(M):
            if dp[graph[i].f] + graph[i].cost > dp[graph[i].to] and dp[graph[i].f] != -float("inf"):
                dp[graph[i].to] = dp[graph[i].f] + graph[i].cost
                flag = True
        if not flag :
            break
def check_p_roop():
    d = [0 for i in range(N)]
    for i in range(N):
        for j in range(M):
            if d[graph[j].f] + graph[j].cost > d[graph[j].to] :
                d[graph[j].to] = d[graph[j].f] + graph[j].cost
                if i == N - 1 :
                    return True
    return False


if __name__ == '__main__':
    N, M = map(int, input().split())
    dp = [-float("inf") for i in range(N)]
    dp[0] = 0
    graph = [0 for _ in range(M)]
    class Edge:
        def __init__(self, f, to, cost):
            self.f = f
            self.to = to
            self.cost = cost
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = Edge(a-1, b-1, c)

    if check_p_roop():
        print("inf")
    else :
        solve()
        print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

for i in range(N):
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
            if b == N and i == N - 1:
                print("inf")
                sys.exit()

print(-distance[N - 1])

Submission status: Wrong Answer

Solution code:
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N and b != N:
        print("inf")
        sys.exit()

print(-distance[N - 1])

Submission status: Wrong Answer

Solution code:
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, c)

distance = [-10 ** 20 - 1] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if -10 ** 9 - 1 != distance[a - 1] and distance[b - 1] < distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N and b != N:
        print("inf")
        sys.exit()

print(distance[N - 1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
N, M = map(int, input().split())

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, c)

distance = [-10 ** 20 - 1] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if -10 ** 9 - 1 != distance[a - 1] and distance[b - 1] < distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N:
        print("inf")
        sys.exit()

print(distance[N - 1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
N, M = map(int, input().split())

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, c)

distance = [-10 ** 15 - 1] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if -10 ** 9 - 1 != distance[a - 1] and distance[b - 1] < distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N:
        print("inf")
        sys.exit()

print(distance[N - 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def BellmanFord(graph: "List[List[int]]", s: int):
    """
    特定の始点から各点への最短距離を求めます。
    重みが負であっても動作します。
    ================
    s: 始点
    graph: 隣接リスト
    ----------------
    第一返り値: 負の閉路があるかいなか
    第二返り値: 最短距離のリスト
    """
    INF = 1e18
    n = len(graph)
    dist = [INF] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(graph[v])):
                e  = graph[v][k]
                if dist[v] != INF and dist[e[0]] > dist[v] + e[1]:
                    dist[e[0]] = dist[v] + e[1]
                    if i == n-1:
                        return True, dist
    return False, dist

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(M):
        G[a[i]-1].append((b[i]-1, c[i]))
    flag, cost = BellmanFord(G, 0)
    if flag:
        print('inf')
    else:
        print(-cost[N-1])
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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] = -1 * int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

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 == 1 and dis + _get_dis(graph, node, 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_dis(graph, key_idx, target_node):
  for node, dis in graph[key_idx]:
    if node == target_node:
      return dis
  
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)):
    idx_options = []
    idx = 0
    for cost, flg in zip(costs, flgs):
      if flg is False:
        idx_options.append([cost, idx])
      idx += 1
    tmp_idx = sorted(idx_options, reverse=True)[0][1]
    queue.append(tmp_idx)
    flgs[tmp_idx] = True
    
    prv_node = queue.popleft()
    
    for node, dis in graph[prv_node]:
      tmp_dis = _get_max_cost(graph, prv_node, node)
      if costs[node] < tmp_dis + costs[prv_node]:
        costs[node] = tmp_dis + costs[prv_node]

  return costs[-1]

def _get_max_cost(graph, start_node, end_node):
  queue = deque()
  queue.append([start_node, 0])
  done = []
  max_cost_options = []
  
  while len(queue) > 0:
    prv_node, total_dis = queue.popleft()
    for node, dis in graph[prv_node]:
      if node == end_node:
        max_cost_options.append(total_dis+dis)
      if node not in done:
        queue.append([node,total_dis+dis])
        done.append(node)
  return max(max_cost_options)
  

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, 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 == 1 and dis + _get_dis(graph, node, 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_dis(graph, key_idx, target_node):
  for node, dis in graph[key_idx]:
    if node == target_node:
      return dis
  


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))