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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
  _from, _to, _cost = map(int, input().split())
  graph[_from].append((_to, _cost))
ans = -2 * 10**12
def search(_from, _total):
  _next = graph[_from]
  global ans
  if len(_next) != 0:
    for node in _next:
      if node[0] == N:
        ans = max(ans, _total+node[1])
      else:
        search(node[0], _total+node[1])

if len(graph[N]) >= 1:
  print('inf')
else:
  search(1, 0)
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)

Submission status: Runtime Error

Solution code:
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

def remove_Edge(N,Ef,Eb,start,goal):
    v = connect_dfs(N,Ef,start) & connect_dfs(N,Eb,goal)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            E[j].pop(i)

def Bellman_Ford(N,E,start,INFTY=10**18):
    def update(dist,N,E,start):
        done = [False]*N
        done[start] = True
        q = [start]
        d = dist[:]
        while q:
            i = q.pop()
            di = d[i]
            for j,c in E[i].items():
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    q.append(j)
                    done[j] = True
        return d
    #
    d = [INFTY]*N
    d[start] = 0
    for _ in range(N-1):
        d = update(d,N,E,start)
    if d!=update(d,N,E,start):
        return None
    else:
        return d

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in [0]*M]
    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    
    remove_Edge(N,E,Eb,0,N-1)
    d = Bellman_Ford(N,E,0)
    if d == None:
        print("inf")
    else:
        print(-d[-1])
    
main()

Submission status: Runtime Error

Solution code:
def main():
    [N, M] = [int(i) for i in input().split()]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen

    dist2 = dist.copy()

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist2[a-1] + c
            if newLen > dist2[b-1]:
                dist2[b-1] = newLen

    if dist != dist2:
        print('inf')
    else:
        print(dist[N-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    [N, M] = [int(i) for i in input().split()]

    E = []

    for i in range(M):
        E.append([int(i) for i in input().split()])

    dist = [-1*10**100 for i in range(N)]
    dist[0] = 0

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist[b-1] = newLen

    dist2 = dist.copy()

    for i in range(N):
        for [a, b, c] in E:
            newLen = dist[a-1] + c
            if newLen > dist[b-1]:
                dist2[b-1] = newLen

    if dist != dist2:
        print('inf')
    else:
        print(dist[N-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_search(self, start):
        # true, dist なら負の経路を含む
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        counter = 0
        while True:
            update = False
            for n in range(N):
                for edge in self.edges[n]:
                    to, cost = edge
                    if d[n] != float('inf') and d[to] > d[n] + cost:
                        d[to] = d[n] + cost
                        update = True
                        counter += 1
            if not update:
                break
            if counter >= self.N ** 2:
                return True, d

        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_search(0)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Submission status: Runtime Error

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_search(self, start):
        # true, dist なら負の経路を含む
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        counter = 0
        while True:
            update = False
            for n in range(N):
                for edge in self.edges[n]:
                    to, cost = edge
                    if d[n] != float('inf') and d[to] > d[n] + cost:
                        d[to] = d[n] + cost
                        update = True
                        counter += 1
            if not update:
                break
            if counter >= self.N ** 2:
                return True, d

        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_bool(0, N)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    
    for i in range(2):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
        if i <= 0: a0 = dist[-1]
    if a0 != dist[-1]: return None, False
    return dist, True


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford(g, 0)

if TF: print(-dist[-1])
else: print("inf")

if n==2 and m==2: assert False

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from collections import defaultdict


def main():
    N, M = readi(2)
    edges = readi(M, 3)
    pred = defaultdict(list)
    for a, b, _ in edges:
        pred[b].append(a)
    # dbg(pred=pred)
    s = set()
    s2 = set()

    def rec(n):
        if n not in s2:
            s2.add(n)
            for m in pred[n]:
                s.add(m)
                rec(m)

    rec(N)
    # dbg(s=s)
    dist = arr(N + 1, fill_value=float("-inf"))
    dist[1] = 0
    for i in range(N):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d > dist[b]:
                if i == N - 1 and b in s:
                    print("inf")
                    return
                dist[b] = new_d
    print(dist[N])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy


def dfs(adj_list, cur_node, visited_nodes):
    visited_nodes.append(cur_node)

    # next_nodes = np.argwhere(adj_mat[cur_node] != 0).flatten()
    next_nodes = adj_list[cur_node]

    if len(next_nodes) == 0:
        # N
        visited_nodes.remove(cur_node)
        return 0

    for tup in next_nodes:
        if tup[0] in visited_nodes:
            visited_nodes.remove(cur_node)
            return np.inf

    # score_max = max([dfs(adj_list, b, visited_nodes) + c
    #                  for b, c in next_nodes])
    scores = []
    for b, c in next_nodes:
        score = dfs(adj_list, b, visited_nodes) + c
        if np.isinf(score):
            visited_nodes.remove(cur_node)
            return np.inf
        scores.append(score)

    score_max = max(scores)

    visited_nodes.remove(cur_node)
    return score_max


def main():
    N, M = map(int, input().split())
    # adj_mat = np.zeros((N, N), dtype=np.int32)
    adj_list = [[] for _ in range(N)]
    a1 = None
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if i == 0:
            a1 = a
        # adj_mat[a, b] = c
        adj_list[a].append((b, c))

    ans = dfs(adj_list, a1, [])
    if np.isinf(ans):
        print('inf')
    else:
        print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy


def dfs(adj_list, cur_node, visited_nodes):
    visited_nodes.append(cur_node)

    # next_nodes = np.argwhere(adj_mat[cur_node] != 0).flatten()
    next_nodes = adj_list[cur_node]
    for tup in next_nodes:
        if tup[0] in visited_nodes:
            return np.inf

    if len(next_nodes) == 0:
        # N
        return 0

    score_max = max([dfs(adj_list, b, visited_nodes) + c
                     for b, c in next_nodes])

    visited_nodes.remove(cur_node)

    return score_max


def main():
    N, M = map(int, input().split())
    # adj_mat = np.zeros((N, N), dtype=np.int32)
    adj_list = [[] for _ in range(N)]
    a1 = None
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if i == 0:
            a1 = a
        # adj_mat[a, b] = c
        adj_list[a].append((b, c))

    ans = dfs(adj_list, a1, [])
    if np.isinf(ans):
        print('inf')
    else:
        print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy


def dfs(adj_list, cur_node, visited_nodes):
    visited_nodes.append(cur_node)

    # next_nodes = np.argwhere(adj_mat[cur_node] != 0).flatten()
    next_nodes = adj_list[cur_node]
    if np.isin([tup[0] for tup in next_nodes], visited_nodes).any():
        return np.inf

    if len(next_nodes) == 0:
        # N
        return 0

    score_max = max([dfs(adj_list, b, visited_nodes) + c
                     for b, c in next_nodes])

    visited_nodes.remove(cur_node)

    return score_max


def main():
    N, M = map(int, input().split())
    # adj_mat = np.zeros((N, N), dtype=np.int32)
    adj_list = [[] for _ in range(N)]
    a1 = None
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if i == 0:
            a1 = a
        # adj_mat[a, b] = c
        adj_list[a].append((b, c))

    ans = dfs(adj_list, a1, [])
    if np.isinf(ans):
        print('inf')
    else:
        print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import copy


def dfs(adj_mat, cur_node, visited_nodes):
    visited_nodes.append(cur_node)

    next_nodes = np.argwhere(adj_mat[cur_node] != 0).flatten()
    if np.isin(next_nodes, visited_nodes).any():
        return np.inf

    if len(next_nodes) == 0:
        # N
        return 0


    score_max = max([dfs(adj_mat, next_node, visited_nodes) + adj_mat[cur_node][next_node]
                     for next_node in next_nodes])

    visited_nodes.remove(cur_node)

    return score_max


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    a1 = None
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if i == 0:
            a1 = a
        adj_mat[a, b] = c

    ans = dfs(adj_mat, a1, [])
    if np.isinf(ans):
        print('inf')
    else:
        print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class BellmanFord():
    """ ベルマンフォード法
    重み付き有向グラフにおける単一始点最短路アルゴリズム
    
    * 使用条件
        - DAG（有向グラフで閉路を持たない）であること
        - 負のコストがあってもOK
    
    * 負の閉路がある場合、最短路は求まらないが、負の閉路の検出はできる
    
    * 計算量はO(V*E)
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合
    
    @property
    def E(self):
        """ 辺数 """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)
    
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False

N,M = list(map(int, input().split()))
bf = BellmanFord()
 
for i in range(M):
    s,e,w=list(map(int,input().split()))
    bf.add(s-1, e-1, -w)

if bf.exist_negative_loop():
    print("inf")
else:
    dist = bf.shortest_path(0)
    print(-dist[-1])

Submission status: Runtime Error

Solution code:
class BellmanFord():
    """ ベルマンフォード法
    重み付き有向グラフにおける単一始点最短路アルゴリズム
    
    * 使用条件
        - DAG（有向グラフで閉路を持たない）であること
        - 負のコストがあってもOK
    
    * 負の閉路がある場合、最短路は求まらないが、負の閉路の検出はできる
    
    * 計算量はO(V*E)
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合
    
    @property
    def E(self):
        """ 辺数 """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)
    
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False

N,M = list(map(int, input().split()))
bf = BellmanFord()

for i in range(M):
    s,e,w=list(map(int,input().split()))
    bf.add(s-1, e-1, -w)

if bf.exist_negative_loop():
    print("inf")
else:
    print(-bf.shortest_path(0)[-1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13
G = [[] for _ in range(N + 1)]
for a, b, c in egdes:
    G[a].append((b, c))

# ループをチェックしてコストが正ならinf
def check_loop(a, b, d):
    if a == b:
        return d > 0
    ret = False
    for to, c in G[a]:
        d += c
        ret |= check_loop(to, b, d)
    return ret


for a, b, c in egdes:
    if a > b:
        if check_loop(a, b, c):
            print('inf')
            exit()

# 動的計画法のために隣接行列
G = [[-INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = c
dp = [-INF] * (N + 10)
dp[1] = 0
for i in range(1, N + 1):
    for j in range(1, i):
        dp[i] = max(dp[i], dp[j] + G[j][i])
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13
G = [[] for _ in range(N + 1)]
for a, b, c in egdes:
    G[a].append((b, c))

# ループをチェックしてコストが正ならinf
def check_loop(a, b, d):
    if a == b:
        return d > 0
    ret = False
    for to, c in G[a]:
        d += c
        ret |= check_loop(to, b, d)
    return ret


for a, b, c in egdes:
    if a > b:
        if check_loop(a, b, 0):
            print('inf')
            exit()

# 動的計画法のために隣接行列
G = [[-INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = c
dp = [-INF] * (N + 10)
dp[1] = 0
for i in range(1, N + 1):
    for j in range(1, i):
        dp[i] = max(dp[i], dp[j] + G[j][i])
print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13
G = [[] for _ in range(N + 1)]
for a, b, c in egdes:
    G[a].append((b, c))

# ループをチェックしてコストが正ならinf
def check_loop(a, b, d):
    if a == b:
        return d > 0
    ret = False
    for to, c in G[a]:
        d += c
        ret |= check_loop(to, b, d)
    return ret


for a, b, c in egdes:
    if a > b:
        if check_loop(a, b, 0):
            print('inf')
            exit()

# 動的計画法のために隣接行列
G = [[-INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = c
dp = [-INF] * (N + 1)
dp[1] = 0
for i in range(1, N + 1):
    for j in range(1, i):
        dp[i] = max(dp[i], dp[j] + G[j][i])
print(dp[N])

Submission status: Runtime Error

Solution code:
def BellmanFord(edges,num_v,source):
  dist=[float("inf") for i in range(num_v)]
  dist[source]=0
  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != float("inf") and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==num_v-1: return -1
  
  return dist

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

d  = BellmanFord(edges,N,0)
d2  = BellmanFord(edges2,N,0)
if d==-1:
    print("inf")
    exit()

for i in range(N):
    if d[i] == float("inf"):
        print("inf")
        exit()

print(max(-d[N-1],d2[N-1]))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

def bellman_ford():
    d = [None] * (N + 1)
    visited = [False] * (N + 1)
    d[1] = 0
    visited[1] = True
    updated = True
    cnt = 0
    
    while updated and (cnt < N):
        updated = False
        cnt += 1
        for u, v, c in edges:
            if (not visited[v]) or (visited[v] and visited[u] and d[v] < d[u] + c):
                d[v] = d[u] + c
                visited[v] = True
                updated = True
                
    return d, cnt

d, cnt = bellman_ford()
print(d[-1] if cnt < N else 'inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

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

Submission status: Runtime Error

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

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

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

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

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

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


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


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

Submission status: Runtime Error

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

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

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

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

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

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


N, M = l_inpl()
edges = []

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

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