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: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
to=[[]for _ in range(n)]
ot=[[]for _ in range(n)]
dic={}
for i in range(m):
    a,b,c=map(int,input().split())
    to[a-1].append([b-1,-c])
    ot[b-1].append([a-1,-c])
#print(to)
vi_to=[0]*n
vi_to[0]=1
from collections import deque
que=deque()
que.append(0)
while que:
    v=que.pop()
    for u,c in to[v]:
        if vi_to[u]:
            continue
        vi_to[u]=1
        que.appendleft(u)

vi_ot=[0]*n
vi_ot[n-1]=1
que=deque()
que.append(n-1)
while que:
    v=que.pop()
    for u,c in ot[v]:
        if vi_ot[u]:
            continue
        vi_ot[u]=1
        que.appendleft(u)

av=[0]*n
for i in range(n):
    if vi_to[i] and vi_ot[i]:
        av[i]=1
#print(av)

dist=[float("inf")]*n
dist[0]=0
for i in range(n):
    for a,toa in enumerate(to):
        for b,c in toa:
            if av[a] and av[b]:
                if dist[b]>dist[a]+c:
                    dist[b]=dist[a]+c
                    if i==n-1:
                        print("inf")
                        exit()
#print(dist)
print(-dist[n-1])

Submission status: Accepted

Solution code:
#!python3

def mii():
    return map(int, input().split())

from heapq import heappush, heappop

def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))

    used = [False] * N
    q = [(0, set())]
    while q:
        p1, s1 = q.pop()

        for p2, x in ab[p1]:
            if p2 in s1:
                print("inf")
                return

            s2 = set(s1)
            s2.add(p2)
            q.append((p2, s2))

    q = []
    heappush(q, (0, 0))
    dp = [10**9*N+1] * N
    while q:
        t1, p1 = heappop(q)

        for p2, t2 in ab[p1]:
            t3 = t1 - t2
            if t3 < dp[p2]:
                dp[p2] = t3
                heappush(q, (t3, p2))

    print(-dp[-1])

def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))


    INF = 10**9*N + 1
    dp = [-INF] * N
    dp[0] = 0
    for i in range(N + 1):
        updated = False
        for p1 in range(N):
            if dp[p1] == -INF: continue

            for p2, t2 in ab[p1]:
                t3 = dp[p1] + t2
                if t3 > dp[p2]:
                    dp[p2] = t3

                    updated = True
        if i == N-1:
            dp0 = dp[-1]
        elif i == N:
            dp1 = dp[-1]
            if dp0 == dp1:
                print(dp1)
            else:
                print("inf")

        if not updated:
            print(dp[-1])
            return



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    # スコアの正負を逆にし、最小値を求める問題に置き換える
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])
    # ベルマン・フォードで最小スコアを計算
    # n-1回やっても更新があるということは負の閉路があるということ
    # 負の閉路がなければ答えを出力して終了
    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                change = True
        if not change:
            print(-score[n - 1])
            exit()
    # 負の閉路がある場合は、その影響がゴールまで届くかをチェック
    reachable = [False] * n
    for _ in range(n):
        for a, b, c in ee:
            if reachable[a]:reachable[b]=True
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                reachable[b] = True
        if reachable[n - 1]:
            print("inf")
            exit()
    print(-score[n-1])

main()

Submission status: Accepted

Solution code:
INF = float('inf')
def bellmanford(n, edges, r):  # r : start
    d = [INF] * n
    d[r] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    return -d[n-1]


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for u, v, cost in edges:
            # INFからは更新しない
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                # 検出した負閉路はすぐに-INFにする
                res[v] = -INF
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res[N-1] != -INF:
    print(-res[N-1])
else:
    print('inf')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res[N-1] != -INF:
    print(-res[N-1])
else:
    print('inf')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    ans = res[N-1]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    if ans != res[N-1]:
        # あったら空リストを返却
        return []
    # 問題なければ頂点リストを返却
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res:
    print(-res[N-1])
else:
    print('inf')

Submission status: Accepted

Solution code:
def bellman_ford(edges, start, n):
    inf = float('INF')
    costs = [inf] * n
    # predecessors = [-1] * n
    costs[start]= 0

    for e in edges:
        u,v,c = e
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c
            # predecessors[v] = u

    ans = costs[-1]
    for u,v,c in edges:
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c

    return -ans if costs[-1] == ans else 'inf'

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

Submission status: Accepted

Solution code:

def bellman_ford(edges, start, n):
    inf = float('INF')
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for e in edges:
            u,v,c = e
            if costs[v] > costs[u] + c:
                costs[v] = costs[u] + c
                predecessors[v] = u

    ans = costs[-1]
    for u,v,c in edges:
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c

    return -ans if costs[-1] == ans else 'inf'

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

Submission status: Accepted

Solution code:
inf = float('INF')

class edge:
    def __init__(self, source, destination, weight):
        self.from_ = source
        self.to_ = destination
        self.weight = weight

    def values(self):
        return self.from_, self.to_, self.weight

def bellman_ford(edges, start, n):
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for u in range(n):
            for v,w in edges[u].items():
                if costs[v] > costs[u] + w:
                    costs[v] = costs[u] + w
                    predecessors[v] = u

    v = n-1
    while v > 0:
        u = predecessors[v]
        if costs[v] > costs[u] + edges[u][v]:
            return 'inf'
        v = u

    return -costs[n-1]

n,m = map(int, input().split())
edges = [{} for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    edges[a-1][b-1] = -c
print(bellman_ford(edges, 0, n))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph import connected_components

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

row, col, val = zip(*ABC)
# -1倍しておいて最短路問題にする
val = [-(x) for x in val]
graph = csr_matrix((val,(row,col)),(N+1,N+1))

# 強連結成分に制限。ここに負閉路があればinf～
find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
# n = 個数、label=各頂点が属する連結成分のラベル[0,0,1,1,1]
n, labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1]) # [False, False, True~]
graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Accepted

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


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

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

Submission status: Accepted

Solution code:
"""

問題:
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1に置いて、プレイヤーのスコアを 0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 aiに駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci加算される。
頂点 Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 Nに移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約:
- 2≦N≦1000
- 1≦M≦min(N(N−1),2000)
- 1≦ai,bi≦N(1≦i≦M)
- ai≠bi(1≦i≦M)
- ai≠ajまたは bi≠bj(1≦i<j≦M)
- −10 ** 9≦ci≦10 ** 9(1≦i≦M)
- ciは整数である。
- 与えられるグラフには、頂点 1から頂点 N への経路が存在する。

検討:
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理:
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計

計算時間:
- ベルマンフォード法の時間計算量はO(NM)
- 解説通りにpythonで実装したらTLE判定...(約2100ms)
- 制約通りでいけば、NM = 1000 * 2000 = 2 * 10 ** 6
- 20msの化け物がいる...
"""

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

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] + c)

for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b]:
            dist[b] = -inf

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

Submission status: Accepted

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

def bellman_ford(g,n):
    INF = 10**15
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            for sa,sb in g[i]:
                res[sa] = min(res[sa],res[i]+sb)
    f = [False for _ in range(n)]
    for _ in range(n+1):
        for i in range(n):
            for sa,sb in g[i]:
                if res[sa] > res[i]+sb:
                    res[sa] = res[i]+sb
                    f[sa] = True
    if f[-1]: return "inf"
    else:return res[-1]*-1

print(bellman_ford(g,n))

Submission status: Accepted

Solution code:
inf=1e13

def bellmanford(E,N):
    score=[inf for i in range(N)]
    score[0]=0
    for i in range(N-1):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])
    temp=score[N-1]
    score = [inf for i in range(N)]
    score[0] = 0
    for i in range(N):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])
    loop=(temp!=score[N-1])

    return temp,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    E=[list(map(int, input().split())) for _ in range(M)]
    negative_E=[]
    for a,b,c in E:
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(negative_E,N)
    if loop:
        print("inf")
    else:
        print(-score)

Submission status: Accepted

Solution code:
import sys
 
inf = float('inf')
 
n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))
 
def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)
 
    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf
 
    return -dist[n-1]
 
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf

    return -dist[n-1]

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
a = []
b = []
c = []
for _ in range(m):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    a.append(ai - 1)
    b.append(bi - 1)
    c.append(-ci)
abc = list(zip(a, b, c))

def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    res = dist[n-1]

    for _ in range(n):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)

    if dist[n-1] == res:
        return -res
    else:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

INF = 10 ** 15

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = list(zip(*[abc] * 3))

def main():
    dist = [INF] * n
    dist[0] = 0
    for _ in range(n - 1):
        for a, b, c in abc:
            a -= 1; b -= 1; c = -c
            if dist[a] == INF:
                continue
            dist[b] = min(dist[b], dist[a] + c)

    res = dist[n-1]

    for _ in range(n - 1):
        for a, b, c in abc:
            a -= 1; b -= 1; c = -c
            if dist[a] == INF:
                continue
            dist[b] = min(dist[b], dist[a] + c)

    if dist[n-1] == res:
        return -res
    else:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    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):
        if i==num_v-1:
            check=dist[n-1]
        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:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    if neg_flg:
        for i in range(num_v):
            for u,v,d in edges:
                if dist[v] > dist[u] + d:
                    dist[v] = dist[u] + d
    if dist[n-1]==check:
        neg_flg=False
    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: Accepted

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 and 1 not in pre:
        print(-dist[n])
    else:
        print('inf')

else:
    print(-dist[n])

Submission status: Accepted

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):
    if s in pre and pre[N] == s and pre[s] == N:
        return True
    count = 0
    p = pre[N]
    while p != s:
        p = pre[p]
        #print(p, pre)
        if p == s and s in pre:
            return True
        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: Accepted

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 and edge[1]-1==N-1: return inf
    
  return -dist[N-1]
  
print(BellmanFord())

Submission status: Accepted

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)

    ##### Infか判定 #####
    is_inf = False
    if is_cycle:
        route_node = V
        while route_node != s:
            route_node = pre[route_node]
            if route_node in cycle_node:
                is_inf = True
                break

    return 'inf' if is_inf else str(-dist[V])


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

    print(bellman_ford(N, E, 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

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
    k = 0
    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
                    if k == N-1 and j == N-1: return (1, [])
        k += 1
        if k == N: return (0, D)
    return (0, D)

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