Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    #グラフの初期化
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    neg_flg=True
                neg[v] = True
    return neg_flg,dist
 

show_flg=False
show_flg=True

n,m=LI()
g=[[] for i in range(n)]

for i in range(m):
    a,b,c=LI_()
    c=-c-1
    g[a].append((b,c))
    #g[b].append((a,c))
    #show((a,b,-c))

fl,d=BellmanFord(g,n,0)
if fl:
    ans='inf'
else:
    ans=-d[n-1]
print(ans)

Submission status: Wrong Answer

Solution code:
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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for _ in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####
    is_cycle = False
    cycle_node = []
    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            cycle_node.append(n1)

    ##### inf判定 #####
    is_inf = False
    if is_cycle:
        route_node = V
        while route_node != s:
            route_node = pre[route_node]
            #print(route_node)
            if route_node in cycle_node:
                is_inf = True
                break

    return (dist, pre, is_cycle, is_inf)

def main():
    E = []
    # グラフの頂点数
    n,m = map(int,input().split())
    # 辺情報
    for _ in range(m):
        a,b,c = map(int,input().split())
        E.append((a,b,-c))
    #始点
        s = 1

    # ベルマンフォードる
    dist, pre, is_cycle, is_inf = bellman_ford(n, E, s)
    """
    # 出力
    print()
    print('##### GRAPH1 (負の閉路なし) #####')
    print('===== start node =====')
    print(s)
    print()
    print('===== dist =====')
    pprint(dist)
    print()
    print('===== pre =====')
    pprint(pre)
    print()
    print('===== is_cycle =====')
    print(is_cycle)
    print('#################################')
    print()
    """
    if is_inf:
        print('inf')
    else:
        print(-min(dist.values()))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for _ in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####
    is_cycle = False
    cycle_node = []
    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            cycle_node.append(n1)

    ##### inf判定 #####
    is_inf = False
    if is_cycle:
        route_node = V
        while route_node != s:
            route_node = pre[route_node]
            print(route_node)
            if route_node in cycle_node:
                is_inf = True
                break

    return (dist, pre, is_cycle, is_inf)

def main():
    E = []
    # グラフの頂点数
    n,m = map(int,input().split())
    # 辺情報
    for _ in range(m):
        a,b,c = map(int,input().split())
        E.append((a,b,-c))
    #始点
        s = 1

    # ベルマンフォードる
    dist, pre, is_cycle, is_inf = bellman_ford(n, E, s)
    """
    # 出力
    print()
    print('##### GRAPH1 (負の閉路なし) #####')
    print('===== start node =====')
    print(s)
    print()
    print('===== dist =====')
    pprint(dist)
    print()
    print('===== pre =====')
    pprint(pre)
    print()
    print('===== is_cycle =====')
    print(is_cycle)
    print('#################################')
    print()
    """
    if is_inf:
        print('inf')
    else:
        print(-min(dist.values()))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for _ in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####
    is_cycle = False
    cycle_node = []
    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            cycle_node.append(n1)

    ##### inf判定 #####
    is_inf = False
    print(cycle_node)
    if is_cycle:
        route_node = V
        while route_node != s:
            route_node = pre[route_node]
            print(route_node)
            if route_node in cycle_node:
                is_inf = True
                break

    return (dist, pre, is_cycle, is_inf)

def main():
    E = []
    # グラフの頂点数
    n,m = map(int,input().split())
    # 辺情報
    for _ in range(m):
        a,b,c = map(int,input().split())
        E.append((a,b,-c))
    #始点
        s = 1

    # ベルマンフォードる
    dist, pre, is_cycle, is_inf = bellman_ford(n, E, s)
    # 出力
    print()
    print('##### GRAPH1 (負の閉路なし) #####')
    print('===== start node =====')
    print(s)
    print()
    print('===== dist =====')
    pprint(dist)
    print()
    print('===== pre =====')
    pprint(pre)
    print()
    print('===== is_cycle =====')
    print(is_cycle)
    print('#################################')
    print()

    if is_inf:
        print('inf')
    else:
        print(-min(dist.values()))


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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return dist, pre, is_cycle


N, M = map(int, input().split())
abc_list = [list(map(int, input().split())) for _ in range(M)]
abc_list = [[abc[0], abc[1], -abc[2]]for abc in abc_list]

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

path_list = [N]
if is_cycle:
    while True:
        next_path = pre[N]
        if next_path in path_list:
            break
        path_list.append(next_path)

if not is_cycle or 1 not in path_list:
    print(-dist[N])
else:
    print('inf')

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return dist, pre, is_cycle


N, M = map(int, input().split())
abc_list = [list(map(int, input().split())) for _ in range(M)]
abc_list = [[abc[0], abc[1], -abc[2]]for abc in abc_list]

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

if not is_cycle or 1 not in pre.keys():
    print(-dist[N])
else:
    print('inf')

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の定義
    INF = 2**63 - 1
    INF = -INF
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w > dist[n2]:
            is_cycle = True

    is_cycle = checkpath(pre, V, s)
            
    return (dist, pre, is_cycle)


def checkpath(pre, N, s):
    count = 0
    p = pre[N]
    if s in pre and pre[N] == s and pre[s] == N:
        return True
    while p != s:
        p = pre[p]
        count += 1
        if count >= N-1:
            return True
    return False

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))
    # 始点
    s = 1

    # ベルマンフォードる
    dist, pre, is_cycle = bellman_ford(N, E, s)

    #print(dist)
    #print(pre)
    #print(is_cycle)
    
    if is_cycle:
        print("inf")
    else:
        print(dist[N])



if __name__ == '__main__':
    main()

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)




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()
print('##### GRAPH2 (負の閉路あり) #####')
print()
print('===== dist =====')
pprint(dist)
print()
print('===== pre =====')
pprint(pre)
print()
print('===== is_cycle =====')
print(is_cycle)
print('#################################')
print()
'''



if is_cycle:
    g = n
    for i in range(n-1):
        g = pre[g]
        if g == 1:
            break

    if g == 1:
        print(-dist[n])
    else:
        print('inf')

else:
    print(-dist[n])

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)




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()
print('##### GRAPH2 (負の閉路あり) #####')
print()
print('===== dist =====')
pprint(dist)
print()
print('===== pre =====')
pprint(pre)
print()
print('===== is_cycle =====')
print(is_cycle)
print('#################################')
print()
'''



if is_cycle:
    g = n
    for i in range(n):
        g = pre[g]
        if g == 1:
            break

    if g == 1:
        print(-dist[n])
    else:
        print('inf')

else:
    print(-dist[n])

Submission status: Wrong Answer

Solution code:
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の定義
    INF = -10 ** 10
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for _ in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)

def main():
    E = []
    # グラフの頂点数
    n,m = map(int,input().split())
    # 辺情報
    for _ in range(m):
        a,b,c = map(int,input().split())
        E.append((a,b,c))
    #始点
        s = 1

    # ベルマンフォードる
    dist, pre, is_cycle = bellman_ford(n, E, s)
    """
    # 出力
    print()
    print('##### GRAPH1 (負の閉路なし) #####')
    print('===== start node =====')
    print(s)
    print()
    print('===== dist =====')
    pprint(dist)
    print()
    print('===== pre =====')
    pprint(pre)
    print()
    print('===== is_cycle =====')
    print(is_cycle)
    print('#################################')
    print()
    """
    if is_cycle:
        print(max(dist.values()))
    else:
        print('inf')


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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return dist, pre, is_cycle


N, M = map(int, input().split())
abc_list = [list(map(int, input().split())) for _ in range(M)]
abc_list = [[abc[0], abc[1], -abc[2]]for abc in abc_list]

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

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

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True
    '''
    return (dist, pre, is_cycle)




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()
print('##### GRAPH2 (負の閉路あり) #####')
print()
print('===== dist =====')
pprint(dist)
print()
print('===== pre =====')
pprint(pre)
print()
print('===== is_cycle =====')
print(is_cycle)
print('#################################')
print()
"""

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

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)




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()
print('##### GRAPH2 (負の閉路あり) #####')
print()
print('===== dist =====')
pprint(dist)
print()
print('===== pre =====')
pprint(pre)
print()
print('===== is_cycle =====')
print(is_cycle)
print('#################################')
print()
"""

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

Submission status: Wrong Answer

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

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            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:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        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))
    # 始点
    s = 1

    # ベルマンフォードる
    dist, pre, is_cycle = bellman_ford(N, E, s)


    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())
ABC = []
for i in range(M):
  a,b,c=map(int,input().split())
  c=-c
  ABC.append([a,b,c])

def BellmanFord():
  inf=float("Inf")
  dist=[inf for i in range(N)]
  dist[0]=0
  
  for i in range(N):
    for edge in ABC:
      if dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==N-1: return inf
    
  return -dist[N-1]
  
print(BellmanFord())

Submission status: Wrong Answer

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

def BellmanFord():
  inf=float("Inf")
  dist=[inf for i in range(N)]
  dist[0]=0
  
  for i in range(N+1):
    for j in range(M):
      edge=ABC[j]
      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==N: return inf
  return -dist[N-1]
  
print(BellmanFord())

Submission status: Wrong Answer

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

def BellmanFord():
  inf=float("Inf")
  dist=[inf for i in range(N)]
  dist[0]=0
  
  for i in range(N):
    for j in range(M):
      edge=ABC[j]
      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==N-1: return inf
  return -dist[N-1]
  
print(BellmanFord())

Submission status: Wrong Answer

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

def BellmanFord():
  inf=float("Inf")
  dist=[inf for i in range(N)]
  dist[0]=0
  
  for i in range(N):
    for j in range(M):
      edge=ABC[j]
      if dist[edge[0]-1]!=inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==N-1: return inf
  return -dist[N-1]
  
print(BellmanFord())

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の定義
    INF = 2**63 - 1
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for i in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] > dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####
    is_cycle = False
    cycle_node = []
    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True
            cycle_node.append(n1)

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