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:
from collections import deque
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 BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c, w in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

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

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

B1 = BFS(N, E1, 0)
B2 = BFS(N, E2, N-1)
B = [0 if B1[i] < 0 or B2[i] < 0 else 1 for i in range(N)]

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

Submission status: Accepted

Solution code:
INF = 10 ** 15


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

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

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

    return ret


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

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

Submission status: Accepted

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

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

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = -1 * int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    for k in e.keys():
      for t in e[k]:
        self.edges.append((k, t[0], t[1]))
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    for i in range(self.n + 1):
      for (u, v, c) in self.edges:
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i == self.n and (v == self.n):
            return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path(1, N)
if res == "-loop": print("inf")
else: print(-res)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

INF = 10**17

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


def bfs(graph, start):
    checked = [False]*N
    checked[start] = True
    q = [start]
    while q:
        qq = []
        for p in q:
            for np in graph[p]:
                if not checked[np]:
                    qq.append(np)
                    checked[np] = True
        q = qq
    return checked

graph1 = [[] for _ in range(N)]
graph2 = [[] for _ in range(N)]
for a, b, e in Edges:
    graph1[a-1].append(b-1)
    graph2[b-1].append(a-1)

checked1 = bfs(graph1, 0)
checked2 = bfs(graph2, N-1)

n_Edges = []
for a, b, e in Edges:
    if checked1[a-1] and checked2[b-1]:
        n_Edges.append((a, b, e))

D = [INF]*N
D[0] = 0
ok = True
for i in range(N):
    update = False
    for a, b, c in n_Edges:
        if D[a-1] != INF and D[b-1] > D[a-1] - c:
            D[b-1] = D[a-1] - c
            update = True
    if i==N-1 and update:
        ok = False

if not ok:
    print('inf')
else:
    print(-D[N-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for i in range(M)]
cost = [-float("inf")] * N
cost[0] = 0

for n in range(N-1):
  for m in range(M):
    a, b, c = edge[m]
    cost[b-1] = max(cost[b-1], cost[a-1] + c)

r = cost[-1]
for m in range(M):
    a, b, c = edge[m]
    cost[b-1] = max(cost[b-1], cost[a-1] + c)

print(r if cost[-1] == r else "inf")

Submission status: Accepted

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

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


    ans = find_negative_loop(N, M, edges)

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

    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = 10 ** 13
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')

Submission status: Accepted

Solution code:
inf = float('inf')

def solve():
    N, M = map(int, input().split())
    edges = [None] * M

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

    ans = BellmanFord(N, M, edges)
    if ans is None:
        print('inf')
    else:
        print(-ans)

def BellmanFord(N, M, edges):
    d = [inf] * N
    d[0] = 0

    for i in range(N-1):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = d[u] + c

    for i in range(N):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = -inf

    if d[N-1] == -inf:
        return None
    else:
        return d[N-1]
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

def BellmanFord(E, N, source):
    #E:E[a]は頂点aを始点とする辺のリストであり、辺の終点bと辺の重みwが(b, w)の形で格納されている
    #N:頂点の数
    #source:始点
    #グラフの初期化
    d = [INF for _ in range(N)]
    d[source] = 0
    
    #辺の緩和
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and edge[0] == N-1:
                        return -1
    
    return d

N, M = MAP()
abc = [LIST() for _ in range(M)]
G = [[] for _ in range(N)]

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

dist = BellmanFord(G, N, 0)
if dist == -1:
	print("inf")
else:
	print(-dist[N-1])

Submission status: Accepted

Solution code:
inf = float('inf')
# ベルマンフォード法 計算量(VE)
# [引数]: 隣接リスト, 始点, 終点
class Bellmanford:
    def __init__(self, to : list, start : int, goal : int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N
    
    # self.distを更新
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
    
    # グラフの負閉路検出
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle
    
    # スタートからゴールまでのパスの負閉路検出
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

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

BF = Bellmanford(to, 0, N-1)
BF.update()

if BF.detection_stog():
    ans = "inf"
else:
    ans = -BF.dist[N-1]

print(ans)

Submission status: Accepted

Solution code:
def bellman_ford(es: list, s: int, inf: int) -> list:
    n = 0
    for e in es: n = max(n, e[0], e[1])
    n += 1
    dis = [inf] * n
    dis[s] = 0
    for t in range(n << 1):
        for e in es:
            if dis[e[0]] != inf and dis[e[1]] > dis[e[0]] + e[2]:
                dis[e[1]] = dis[e[0]] + e[2]
                if t + 1 >= n: dis[e[1]] = -inf
    return dis

if __name__ == '__main__':
    N, M = map(int, input().split())
    es = []
    for i in range(M):
        a, b, c = map(int, input().split())
        es.append((a - 1, b - 1, -c))
    INF = 1 << 60
    dis = bellman_ford(es, 0, INF)
    if dis[N - 1] == -INF: print("inf")
    else: print(-dis[N - 1])

Submission status: Accepted

Solution code:


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

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

INF = float("inf")
d = [INF] * N
d[0] = 0
"""
最大経路探索的な問題
よくあるベルマンフォード法なら、コストが正の値で、負の閉路が見つかったら失敗、という形で最小経路を求めることになる。
今回は最長経路なので、正の閉路が求まったら失敗にしたい。
なので
・コストを負の値でもつ。表示するときに正に変える
・コストを負にするので閉路を見つけられる
みたいな形にする
"""

def solve(start):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) < d[b]:
                d[b] = d[a] + (-c)
                # 最後まで確認しても更新されたら閉路あり
                if i == N-1 and b == N-1:
                    return "inf"

    return -1*d[-1]

print(solve(0))

Submission status: Accepted

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

def bellman_ford(s,v,e,es):
    #s:始点　v:頂点数　e:辺の数　es:[s,t,c]
    d = [float("inf")]*v
    d[s] = 0

    for i in range(n):
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                if i==n-1 and q==n-1:
                    print("inf")
                    exit()
    return d

d=bellman_ford(0,n,m,es)
print(-d[n-1])

Submission status: Accepted

Solution code:
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         is_cycle = False

    # (2)startとendのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

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

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

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

dist = [inf] * N
dist[0] = 0
for _ in range(N-1):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w

is_update = [False] * N
for _ in range(N):
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            dist[nv] = dist[v] + w
            is_update[nv] = True
        if is_update[v] is True:
            is_update[nv] = True

if is_update[N-1] is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return dist[n - 1]
    if n - 1 in v_nows:
        return 'inf'
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        for v, c in G[u]:
            if v == n - 1:
                return 'inf'
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))

Submission status: Accepted

Solution code:
def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance[:]
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            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 or loop_cnt > n: break
    return d

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

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

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

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, -c))
    
    
#ベルマンフォード法:負閉路の検出とある一点から他のすべての点への最短距離の算出

def BellmanFord(E, N, source):
    #E:E[a]は頂点aを始点とする辺のリストであり、辺の終点bと辺の重みwが(b, w)の形で格納されている
    #N:頂点の数
    #source:始点
    #グラフの初期化
    inf = 10**20
    d = [inf for _ in range(N)]
    d[source] = 0
    
    #辺の緩和
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and edge[0] == N-1:
                        return -1
    
    return d

dist = BellmanFord(E, N, 0)
if dist == -1:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        E[a].append((b,-c))
        R[b].append((a,-c))

    from collections import deque
    state=[0]*n
    state[0]=1
    state[n-1]=2

    Q=deque([0])
    while(Q):
        v=Q.popleft()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    Q=deque([n-1])
    while(Q):
        v=Q.popleft()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        for v in range(n):
            if(state[v]!=3): continue
            for nv,w in E[v]:
                if(state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    if(k==n-1):
                        print("inf")
                        return
    print(-dist[-1])
resolve()

Submission status: Accepted

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

inf=float("inf")
data=[-inf]*(n+1)
data[1]=0
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

lst=data[:]
for i in range(n):
    for a,b,c in abc:
        if data[a]!=inf:
            data[b]=max(data[b],data[a]+c)

que=[]
for i in range(1,n+1):
    if lst[i]!=data[i]:
        que.append(i)
        
flag=[0]*(n+1)
for u in que:
    flag[u]=1

li=[[] for i in range(n+1)]
for a,b,c in abc:
    li[a].append(b)

while que:
    h=que.pop()
    for u in li[h]:
        if flag[u]==0:
            flag[u]=1
            que.append(u)

if flag[n]==1:
    print("inf")
else:
    print(data[n])

Submission status: Accepted

Solution code:
INF = 10**18

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

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

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                if _==N-1:
                    update = adj
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    visited = [0 for _ in range(N)]
    visited[update] = 1
    stack = [update]
    while stack:
        node = stack.pop()
        for adj,c in graph[node]:
            if not visited[adj]:
                visited[adj] = 1
                stack.append(adj)
    if visited[N-1]:
        print('inf')
    else:
        print(-dist[N-1])

Submission status: Accepted

Solution code:
def bellman_ford(edges, num_v, start, end):
    """
    ベルマンフォード法
    :param edges: (from, to, cost)のリスト
    :param num_v: 頂点の数
    :param start: 始点
    :param end: 終点
    :return: 最小コスト
    """
    inf = float("inf")
    dist = [inf] * num_v
    dist[start - 1] = 0
    ans = -1

    for i in range(num_v):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == num_v - 1 and ans != dist[end - 1]:
                    return -1
        if i == num_v - 2:
            ans = dist[end - 1]

    return ans


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

    ans = bellman_ford(edges, n, 1, n)
    print(-ans if ans != -1 else "inf")


if __name__ == '__main__':
    abc061_d()

Submission status: Accepted

Solution code:
def abc061_d():
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]

    inf = float("inf")
    result = [inf] * n
    result[0] = 0

    for i in range(n - 1):
        for f, t, c in edges:
            result[t - 1] = min(result[t - 1], result[f - 1] - c)
    ans = result[n - 1]
    for f, t, c in edges:
        result[t - 1] = min(result[t - 1], result[f - 1] - c)
    print(-ans if ans == result[n - 1] else "inf")


if __name__ == '__main__':
    abc061_d()

Submission status: Accepted

Solution code:
(n,m),*l=[list(map(int,s.split()))for s in open(0)];d=[0]*2+[9e99]*n
for i in range(n*2):
 for a,b,c in l:d[b]=min(d[b],d[a]-c)
 if i==n:x=d[n]
print([-x,'inf'][d[n]!=x])

Submission status: Accepted

Solution code:
(n,m),*l=[list(map(int,s.split()))for s in open(0)];d=[0]*2+[9e99]*n
for i in range(n*2):
 for a,b,c in l:
  if d[b]>d[a]-c:d[b]=[d[a]-c,-9e99][i>n]
 if i==n:x=d[n]
print([-x,'inf'][d[n]!=x])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[float('inf')]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
x=distance[n-1]
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=-float('inf')
if distance[n-1]==x:
  print(-distance[n-1])
else:
  print('inf')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[9999999999999999]*n
distance[0]=0
for i in range(n-1):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
f=[0]*n
for i in range(n):
  for j in range(m):
    if distance[l[j][1]-1]>distance[l[j][0]-1]-l[j][2]:
      distance[l[j][1]-1]=distance[l[j][0]-1]-l[j][2]
      f[l[j][1]-1]=1
    if f[l[j][0]-1]==1:
      f[l[j][1]-1]=1
if f[n-1]==0:
  print(-distance[n-1])
else:
  print('inf')

Submission status: Accepted

Solution code:
INF = float("inf")

def bellman_ford(edges, n, s):
    d = [0] + [INF] * (n-1)
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            if d[t] > d[f] + c:
                if i == n-1: d[t] = -INF
                else: d[t] = d[f] + c
    for i in range(n):
        for f, t, c in edges:
            if d[f] == INF: continue
            d[t] = min(d[t], d[f] + c)
    return d

n, m = map(int, input().split())
es = [None] * m
for i in range(m):
    f, t, c = map(int, input().split())
    es[i] = (f-1, t-1, -c)

d = bellman_ford(es, n, 0)
print(-d[n-1])

Submission status: Accepted

Solution code:
def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0
    for _ in range(num):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return (-1,cost)
    return (1,-cost[goal])

def examD(inf):
    N, M = LI()
    v = []
    for i in range(M):
        x, y, z = map(int, input().split())
        v.append((x-1,y-1,-z))
#    print(v)
#    print(bellmanford(N, 0, N-1, v))
    cur,d = bellmanford(N, 0, N-1, v)
    if cur==-1:
        inf_flag = [False]*N
        for i in range(N):
            for f, t, c in v:
                if d[f] == inf: continue
                if inf_flag[f] == True:
                    inf_flag[t] = True
                if d[t] > d[f] + c:
                    d[t] = d[f] + c
                    inf_flag[t] = True
        print("inf" if inf_flag[N-1] else -d[N-1])
    else:
        print(d)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(inf)

Submission status: Accepted

Solution code:
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)

INF = float("inf")
d = [INF] * n
d[0] = 0

for i in range(n-1):
    for f, t, c in edges:
        if d[f] == INF: continue
        d[t] = min(d[t], d[f] + c)

inf_flag = [False] * n

for i in range(n):
    for f, t, c in edges:
        if d[f] == INF: continue
        if inf_flag[f] == True:
            inf_flag[t] = True
        if d[t] > d[f] + c:
            d[t] = d[f] + c
            inf_flag[t] = True

print("inf" if inf_flag[n-1] else -d[n-1])