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:
# coding:utf-8
from pprint import pprint


def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: INF)
    dist[s] = 0
    pre = {}
    is_cycle = False

    # 最短経路算出
    for _ in range(V-1):
        update = False
        for n1, n2, w in E:
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1
                update = True
        if not update:
            break

    # 負の閉路検出
    for n1, n2, w in E:
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)


def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    # print()
    # pprint(dist)
    # print()
    # pprint(pre)
    # print()
    # print(is_cycle)
    # print()

    if is_cycle:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: INF)
    dist[s] = 0
    pre = {}
    is_cycle = False

    # 最短経路算出
    for loop_num in range(V):
        update = True
        for n1, n2, w in E:
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1
                update = True
                if loop_num == V - 1:
                    is_cycle = True
                    break
        if not update:
            break

    return (dist, pre, is_cycle)


def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    if is_cycle:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: -INF)
    dist[s] = 0
    pre = {}
    is_cycle = False

    # 最短経路算出
    for num in range(V):
        for n1, n2, w in E:
            if dist[n1] != -INF and dist[n2] < dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    # 負の閉路の検証
    for n1, n2, w in E:
        if dist[n1] + w > dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)

def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    if is_cycle:
        print('inf')
    else:
        print(dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: INF)
    dist[s] = 0
    pre = {}
    is_cycle = False

    for num in range(V):
        update = False
        for n1, n2, w in E:
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1
                update = True
        if not update:
            break
        if num == V-1:
            is_cycle = True

    return (dist, pre, is_cycle)


def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    if is_cycle:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: INF)
    dist[s] = 0
    pre = {}

    # 最短経路の算出
    for i in range(V):
        for n1, n2, w in E:
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    # 負閉路の検出
    is_cycle = False
    for n1, n2, w in E:
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            break

    return (dist, pre, is_cycle)


def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    if is_cycle:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    # 前処理
    from collections import defaultdict
    INF = 2**63 - 1
    dist = defaultdict(lambda: INF)
    dist[s] = 0
    pre = {}

    # 最短経路の算出
    for i in range(V):
        for n1, n2, w in E:
            if dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    # 負閉路の検出
    is_cycle = False
    for n1, n2, w in E:
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            break

    return (dist, pre, is_cycle)


def main():
    # 頂点，辺の数
    N, M = map(int, input().split(' '))
    # 辺の情報
    E = []
    for _ in range(M):
        a, b, c = map(int, input().split(' '))
        E.append((a, b, -c))

    dist, pre, is_cycle = bellman_ford(N, E, 1)

    if is_cycle:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
    return D

def bellman_ford_check(n, E, s=0):
    D = [0] * n
    for k in range(n):
        for i in range(n):
            for j, c in E[i]:
                if D[j] > D[i] + c:
                    D[j] = D[i] + c
                    if k == n-1: return 1
    return 0

if bellman_ford_check(N, E):
    print("inf")
else:
    D = bellman_ford(N, E)
    print(-D[-1])

Submission status: Wrong Answer

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

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
    return D

def bellman_ford_check(n, E, s=0):
    D = [0] * n
    for k in range(n):
        for i in range(n):
            for j, c in E[i]:
                if D[j] > D[i] + c:
                    D[j] = D[i] + c
                    if k == n-1: return 1
    return 0

if bellman_ford_check(N, E1):
    print("inf")
else:
    D = bellman_ford(N, E1)
    print(-D[-1])

Submission status: Wrong Answer

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

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
    return D

def bellman_ford_check(n, E, s=0):
    D = [0] * n
    for k in range(n):
        for i in range(n):
            for j, c in E[i]:
                if D[j] > D[i] + c:
                    D[j] = D[i] + c
                    if k == n-1: return 1
    return 0

if bellman_ford_check(N, E1):
    print("inf")
else:
    D = bellman_ford(N, E1)
    print(-D[-1])

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    matrix = [[10**10]*(N+1) for _ in range(N+1)]
    for i in range(M):
        matrix[a[i]][b[i]] = -c[i] 

    try:
      dist_matrix = bellman_ford(csgraph=csr_matrix(matrix),indices = [1],directed=True)
      print(int(-dist_matrix[0][N]))
    except:
      print('inf')
    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
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    matrix = [[10**10]*(N+1) for _ in range(N+1)]
    for i in range(M):
        matrix[a[i]][b[i]] = -c[i] 

    try:
        dist_matrix = bellman_ford(csgraph=csr_matrix(matrix), indices = 1,directed=True)
        print(int(-dist_matrix[N]))
    except:
        print('inf')
        return 

    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:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M= map(int, input().split())
P = 0
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print("inf")
          exit(0)
dfs(1)
print(max(earn[N], 0))

Submission status: Wrong Answer

Solution code:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M= map(int, input().split())
P = 0
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c))
vis = [0] * (N + 1)
def dfs(x):
  global vis
  vis[x] = 1
  for y in e[x]:
    if y[1] != float("inf"):
      if vis[y[0]] == 1:
        #print("inf")
        exit(0)
      dfs(y[0])
  vis[x] = 0
dfs(1)
def blmnfrd(n, e, s, t):
  path = [float("inf")] * (n + 1)
  path[s] = 0
  edges = []
  for k in e.keys():
    for v in e[k]:
      edges.append((k, v[0], v[1]))
  for _ in range(n):
    for x in edges:
      if path[x[0]] != float("inf") and path[x[1]] > path[x[0]] + x[2]:
        path[x[1]] = path[x[0]] + x[2]
  return path[t]

print(-blmnfrd(N, e, 1, N))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c))
vis = [0] * (N + 1)
def dfs(x):
  global vis
  vis[x] = 1
  for y in e[x]:
    if y[1] != float("inf"):
      if vis[y[0]] == 1:
        print("inf")
        exit(0)
      dfs(y[0])
  vis[x] = 0
dfs(1)
def blmnfrd(n, e, s, t):
  path = [float("inf")] * (n + 1)
  path[s] = 0
  edges = []
  for k in e.keys():
    for v in e[k]:
      edges.append((k, v[0], v[1]))
  for _ in range(n):
    for x in edges:
      if path[x[0]] != float("inf") and path[x[1]] > path[x[0]] + x[2]:
        path[x[1]] = path[x[0]] + x[2]
  return path[t]

print(-blmnfrd(N, e, 1, N))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c))
vis = [0] * (N + 1)
def dfs(x):
  global vis
  vis[x] = 1
  for y in e[x]:
    if y[1] != float("inf"):
      if vis[y[0]] == 1:
        print("inf")
        exit(0)
      dfs(y[0])
  vis[x] = 0
dfs(1)
def blmnfrd(n, e, s, t):
  path = [float("inf")] * (n + 1)
  path[s] = 0
  edges = []
  for k in e.keys():
    for v in e[k]:
      edges.append((k, v[0], v[1]))
  while True:
    update = 0
    for x in edges:
      if path[x[0]] != float("inf") and path[x[1]] > path[x[0]] + x[2]:
        path[x[1]] = path[x[0]] + x[2]
        update = 1
    if update == 0: break
  return path[t]

print(-blmnfrd(N, e, 1, N))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  d[i][i] = 0
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = -c
vis = [0] * (N + 1)
def dfs(x):
  global vis
  vis[x] = 1
  for y in range(N + 1):
    if x == y: continue
    if d[x][y] != float("inf"):
      if vis[y] == 1:
        print("inf")
        exit(0)
      dfs(y)
  vis[x] = 0
dfs(1)
for k in range(N + 1):
  for j in range(N + 1):
    d[1][j] = min(d[1][k] + d[k][j], d[1][j])
print(-d[1][N])

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [0 for i in range(n)]
res = True
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            flg = True
if flg:
    print("inf")
else:
    d = [-INF for i in range(n)]
    d[0] = 0
    res = True
    for i in range(n):
        flg = False
        for _from, _to, cost in edge_ls:
            if d[_to] < d[_from] + cost and d[_from] != -INF:
                d[_to] = d[_from] + cost
                flg = True
    print(d[-1])

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

edge_ls.sort(key=lambda x:x[0])
INF = 10 ** 20
d = [0 for i in range(n)]
res = True
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            flg = True
if flg:
    print("inf")
else:
    d = [-INF for i in range(n)]
    d[0] = 0
    res = True
    for i in range(n):
        flg = False
        for _from, _to, cost in edge_ls:
            if d[_to] < d[_from] + cost and d[_from] != -INF:
                d[_to] = d[_from] + cost
                flg = True
    print(d[-1])

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = 10 ** 20
d = [0 for i in range(n)]
res = True
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            flg = True
if flg:
    print("inf")
else:
    d = [-INF for i in range(n)]
    d[0] = 0
    res = True
    for i in range(n):
        flg = False
        for _from, _to, cost in edge_ls:
            if d[_to] < d[_from] + cost and d[_from] != -INF:
                d[_to] = d[_from] + cost
                flg = True
    print(d[-1])

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))
cnt = 0
INF = 10 ** 20
d = [-INF for i in range(n)]
d[0] = 0
res = True
while cnt <= n-1:
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            flg = True
    cnt += 1
if not flg:
    print(d[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))
cnt = 0
INF = 10 ** 20
d = [-INF for i in range(n)]
d[0] = 0
res = True
while cnt <= n-1:
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_to] != -INF:
            d[_to] = d[_from] + cost
            flg = True
    cnt += 1
if not flg:
    print(d[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))
cnt = 0
INF = 10 ** 20
d = [-INF for i in range(n)]
d[0] = 0
res = True
while cnt <= n-1:
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost:
            d[_to] = d[_from] + cost
            flg = True
    if cnt == n - 1 and flg:
        res = False
        break
    if not flg:
        break
    cnt += 1
if res:
    print(d[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))
cnt = 0
INF = 10 ** 18
d = [-INF for i in range(n)]
d[0] = 0
res = True
while cnt <= n-1:
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost:
            d[_to] = d[_from] + cost
            flg = True
    if cnt == n - 1 and flg:
        res = False
        break
    cnt += 1
if res:
    print(d[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))
cnt = 0
INF = 10 ** 18
d = [-INF for i in range(n)]
d[0] = 0
res = True
while cnt <= n:
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost:
            d[_to] = d[_from] + cost
            flg = True
    if cnt == n and flg:
        res = False
        break
    cnt += 1
if res:
    print(d[-1])
else:
    print("inf")

Submission status: Wrong Answer

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
# dist = floyd_warshall(cost)
# print(int(-1 * dist[0][n-1]))
print('inf')

Submission status: Wrong Answer

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
try:
    dist = floyd_warshall(cost)
    print(int(round(-1 * dist[0][n-1])))
except:
    print('inf')

Submission status: Wrong Answer

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
try:
    dist = floyd_warshall(cost)
    print(round(-1 * dist[0][n-1]))
except:
    print('inf')

Submission status: Wrong Answer

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
try:
    dist = floyd_warshall(cost)
    print(-1 * int(dist[0][n-1]))
except:
    print('inf')

Submission status: Wrong Answer

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

cost = [[0] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
try:
    dist = floyd_warshall(cost)
    print(-1 * int(dist[0][n-1]))
except:
    print('inf')

Submission status: Wrong Answer

Solution code:
def find_negative_loop(n, w, edges):
    d = [float('inf')] * n
    d[0] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                if i == n - 1 and u == n - 1:
                    return None
    return d[n-1]

def main():
    N, M = map(int, input().split())
    edges = [None] * M
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edges[i] = (a, b, -c)


    ans = find_negative_loop(N, M, edges)

    if ans:
        print(-1 * ans)
    else:
        print('inf')

    
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def find_negative_loop(n, w, edges):
    d = [float('inf')] * n
    d[0] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                if i == n - 1:
                    return None
    return d[n-1]

def main():
    N, M = map(int, input().split())
    edges = [None] * M
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edges[i] = (a, b, -c)


    ans = find_negative_loop(N, M, edges)

    if ans:
        print(-ans)
    else:
        print('inf')

    
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s; num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]]*num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist

# class BellmanFord:
#     INF = int(1e18)
#     N = -1
#     edge = []
#     def __init__(self, N):
#         self.N = N
#     def add_edge(self, frm, to, cost):
#         self.edge.append((frm, to, cost));
#     def add_bi_edge(self, a, b, cost):
#         self.add_edge(a, b, cost)
#         self.add_edge(b, a, cost)
#     def calcD(self, start):
#         D = [self.INF] * self.N
#         D[start] = 0
#         update, cnt = True, 0
#         while update:
#             update = False
#             cnt = cnt + 1
#             if cnt > self.N:
#                 return None
#             for frm, to, cost in self.edge:
#                 ncost = D[frm] + cost
#                 if D[frm] == self.INF or ncost >= D[to]:
#                     continue
#                 D[to] = ncost
#                 update = True
#         return D

def BellmanFord(edges, num_v, source):
  #グラフの初期化
  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()
abc = [LIST() for _ in range(M)]
G = []

for a, b, c in abc:
	G.append((a-1, b-1, -c))

dist = BellmanFord(G, N, 0)
if dist == -1:
	print("inf")
else:
	print(-min(dist))
# dist = SPFA(N, G, 0)
# if dist is None:
#     print("inf")
# else:
#     print(-dist[N-1])