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 collections
import heapq
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a-1][b-1] = -c

    dist = [float('inf') for _ in range(N)]
    dist[0] = 0
    for _ in range(N-1):
        for a in graph:
            for b in graph[a]:
                dist[b] = min(dist[b], dist[a]+graph[a][b])
    ans = dist[N-1]

    negative = [False for _ in range(N)]
    for _ in range(N):
        for a in graph:
            if dist[a] != float('inf'):
                for b in graph[a]:
                    if dist[b] > dist[a] + graph[a][b]:
                        dist[b] = dist[a] + graph[a][b]
                        negative[b] = True
                    if negative[a] == True:
                        negative[b] = True
    if negative[N-1]:
        return 'inf'
    else:
        return -ans

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

Submission status: Accepted

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

for i in range(m):
    A[i][2] = -A[i][2]

P = [float("inf")] * (n+1)
P[1] = 0
F = [[0] * 2 for i in range(n+1)]
F[1][0] = 1
F[n][1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans0 = P[:]

for i in range(1):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans1 = P[:]

#print(F)

def d():
    for i in range(n+1):
        if F[i] == [1, 1] and ans1[i] < ans0[i]:
            return "inf"
    return -ans0[n]

print(d())

Submission status: Accepted

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

for i in range(m):
    A[i][2] = -A[i][2]

P = [float("inf")] * (n+1)
P[1] = 0
F = [[0] * 2 for i in range(n+1)]
F[1][0] = 1
F[n][1] = 1

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans0 = P[:]

for i in range(n):
    for j in range(m):
        if F[A[j][0]][0] == 1 :
            F[A[j][1]][0] = 1
        if F[A[j][1]][1] == 1 :
            F[A[j][0]][1] = 1
        P[A[j][1]] = min(P[A[j][1]], P[A[j][0]] + A[j][2])

ans1 = P[:]

#print(F)

def d():
    for i in range(n+1):
        if F[i] == [1, 1] and ans1[i] < ans0[i]:
            return "inf"
    return -ans0[n]

print(d())

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edge = []
for _ in range(m):
  a,b,c = map(int,input().split())
  edge.append((a,b,-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
f = 0
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        f = 1
ans = dis[n]
if f:
  for _ in range(n):
    for a,b,c in edge:
      if dis[b] > dis[a] + c:
        dis[b] = dis[a] + c
        if b == n:
          print("inf")
          exit(0)
print(-ans)

Submission status: Accepted

Solution code:
def main():
    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])

    d = [float('inf')] * N
    d[0] = 0

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N-1]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    if ans == d[N-1]:
        print(-ans)
    else:
        print('inf')


main()

Submission status: Accepted

Solution code:
import sys

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

graph = [0] * (M)
for m in range(M):
    a, b, c = map(int, input().split())
    graph[m] = (a, b, -c)

INF = 1e18
distance = [INF] * N
distance[0] = 0

for n in range(N):
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            if b == N and n == N - 1:
                print("inf")
                sys.exit()

print(-distance[N - 1])

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


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
input=sys.stdin.readline
n,m=map(int,input().split())
graph=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    graph.append([a-1,b-1,-c])

def BellmanFord(n,m,graph):
    costs=[float("inf")]*n
    costs[0]=0
    for _ in range(n-1):
        for i in range(m):
            if costs[graph[i][1]]>costs[graph[i][0]]+graph[i][2]:
                costs[graph[i][1]]=costs[graph[i][0]]+graph[i][2]
    newcosts=[]
    for i in costs:
        newcosts.append(i)
    for _ in range(n):
        for i in range(m):
            if newcosts[graph[i][1]]>newcosts[graph[i][0]]+graph[i][2]:
                newcosts[graph[i][1]]=newcosts[graph[i][0]]+graph[i][2]
    if newcosts[n-1]!=costs[n-1]:
        return "inf"
    else:
        return -costs[n-1]

print(BellmanFord(n,m,graph))

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())
    edges.append((a - 1, b - 1, c))
d = [-inf] * N
d[0] = 0
for i in range(N):
    for a, b, c in edges:
        if d[b] < d[a] + c:
            d[b] = d[a] + c
for i in range(N):
    for a, b, c in edges:
        if d[b] < d[a] + c:
            d[b] = inf
print(d[N - 1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for i in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
                if i==v-1 and b==v-1:
                    return -1
        # 更新が無ければbreak
        if not f:
            break

    return d
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    e.append((a-1,b-1,-c))

ans=bellman_ford(n,0,e)
if ans==-1:
    print("inf")
else:
    print(-ans[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
abc=[]
for i in range(m):
    abc.append([int(j) for j in input().split()])
b=[float("INF")]*(n+1)
b[1]=0
for i in range(1,n+1):
    for s,t,u in abc:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:
                print("inf")
                exit()
print(-b[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         
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*(-1)])
  
temp, d = find_negative_loop(0, n, m ,es)
if temp == d:
  print(d*(-1))
else:
  print('inf')

Submission status: Accepted

Solution code:
n,m=map(int,input().split());a,b=[list(map(int,input().split()))for i in range(m)],[float("INF")]*(n+1);b[1]=0
for i in range(1,n+1):
    for s,t,u in a:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:print("inf");exit()
print(-b[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC61 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    dist = [-inf for _ in range(n)]
    dist[start] = 0
    for cnt in range(n+1):
        for edge in edges:
            e_from, e_to, e_cost = edge
            if dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
        if cnt == n - 1:
            d = dist[:]
    if d[-1] < dist[-1]:
        print('inf')
        quit()
    else:
        return d[-1]

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

ans = Bellman_Ford(edges,0)
print(ans)

Submission status: Accepted

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford() -> int or None:
    dist = [-float("inf")] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] + w > dist[u]:
                dist[u] = dist[v] + w
                if i == N - 1 and u == N:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    global N, M, E
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford()
    flg = ans is not None
    print(ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford() -> int or None:
    dist = [float("inf")] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    global N, M, E
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford()
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC061D - Score Attack
import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    # relax edges
    for i in range(N):
        for v, u, w in E:  # w: positive -> -w
            if v != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  # detect negative cycles
                    return None
    return dist[-1]


def main():
    # reverse weights -> shortest path problem containing negative cycles
    N, M = tuple(map(int, input().split()))  # vertices, edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    # Nから到達できる辺のみ抽出する
    g = nlist([N + 1], [])
    for a, b, c in ABC:
        g[b] += [(a, c)]

    que, rch = [N], {N}
    while que:
        cur = que.pop()
        for nxt, _ in g[cur]:
            if nxt in rch: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    # ベルマンフォード法で負の最短経路(スコアの最大値)を導出する
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        # 負の閉路を除外する
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    # Nから到達できる辺のみ抽出する
    g = nlist([N + 1], [])
    for a, b, c in ABC:
        g[b] += [(a, c)]

    que, arl, rch = [N], [False] * (N + 1), {N}
    while que:
        cur = que.pop()
        if arl[cur]: continue
        arl[cur] = True
        for nxt, _ in g[cur]:
            if arl[nxt]: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    # ベルマンフォード法で負の最短経路(スコアの最大値)を導出する
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        # 負の閉路を除外する
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a-1, b-1, -c))
            
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
        
    ans = dist[-1]
    
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
            
    if ans != dist[-1]:
        print('inf')
    else:
        print(-ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a, b, -c))
        
    for i in range(N-1):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            dist[b-1] = min(dist[b-1], dist[a-1]+c)
            
    ans = dist[-1]
    negative = [False] * N
    
    for i in range(N):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            elif dist[b-1] > dist[a-1]+c:
                dist[b-1] = dist[a-1]+c
                negative[b-1] = True
            if negative[a-1]:
                negative[b-1] = True
            
    if negative[-1]:
        print('inf')
    else:
        print(-ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    if a <= c <= b:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    n, m = LI()
    e = defaultdict(int)
    for i in range(1, n + 1): e[i] = 0
    for i in range(m):
        a, b = LI()
        e[a] += 1
        e[b] += 1
    for i in e.values():
        print(i)
    return

#C
def C():
    n, k = LI()
    d = defaultdict(int)
    for i in range(1, 10**5+1): d[i] = 0
    for i in range(n):
        a, b = LI()
        d[a] += b
    for key, valus in d.items():
        k -= valus
        if k <= 0:
            print(key)
            return
    return

#D
def D():
    n, m = LI()
    abc = LIR_(m)
    for i in range(m):
        abc[i][2] = -abc[i][2] - 1
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n - 1):
        for a, b, c in abc:
            dist[b] = min(dist[a] + c , dist[b])
    check = [False] * n
    for _ in range(n):
        for a, b, c in abc:
            if check[a]:
                check[b] = True
            if dist[b] > dist[a] + c:
                check[b] = True
                dist[b] = dist[a] + c
    if check[n - 1]:
        print("inf")
    else:
        print(-dist[n - 1])
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())

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

    INF = int(1E18)

    D = [INF for _ in range(N)]
    D[0] = 0

    for c in range(N-1):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                D[j] = D[i] + d
                update = True
        if not update:
            break

    negative = [False for _ in range(N)]
    for c in range(N):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                update = True
                D[j] = D[i] + d
                negative[j] = True
        if not update:
            break
    if negative[N-1]:
        print('inf')
    else:
        print(-D[N-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
inf = 10 ** 20
n, m = map(int, input().split())
a_list = []
d = [-inf for _ in range(n)]
d[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list.append([a, b, c])
    d[b] = max(d[a] + c, d[b])
temp = d[-1]
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
if temp != d[-1]:
    print("inf")
else:
    print(d[-1])

Submission status: Accepted

Solution code:
inf = 10 ** 20
n, m = map(int, input().split())
a_list = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list.append([a, b, c])
a_list[0][0] = 0
d = [-inf for _ in range(n)]
d[0] = 0
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
temp = d[-1]
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
if temp != d[-1]:
    print("inf")
else:
    print(d[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            return None

        s, t, w = edge
        self.E[s].append([t, w])
        return True


def BellmanFord(g: Graph, s):
    """ベルマンフォード法によって最短経路を求める
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    # 辺の緩和
    for i in range(N):
        for from_ in range(N):      # ここの２重ループはO(M)
            for to_, weight in g.E[from_]:
                if dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
                    if i == N-1 and to_ == N-1:
                        return None, None

    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for f, t, w in zip(a, b, c):
        g.add_edge([f-1, t-1, -w])

    dist, prev = BellmanFord(g, 0)

    if dist == None:
        print("inf")
    else:
        print(-dist[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] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
m=csr_matrix
n,*t=map(int,open(0).read().split())
s=[n+1]*2
r,c,d=t[1::3],t[2::3],[-c for c in t[3::3]]
u=set(csgraph.depth_first_order(m((d,(c,r)),s),n,1,0))
r,c,d=zip(*[(r,c,d)for r,c,d in zip(r,c,d)if r in u and c in u])
try:print(-int(csgraph.bellman_ford(m((d,(r,c)),s),1,[1])[0,n]))
except:print('inf')

Submission status: Accepted

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

d = [float('inf')] * n
d[0] = 0

for x in range(n * 2):
    for i in range(m):
        if d[a[i]] + c[i] < d[b[i]]:
            d[b[i]] = d[a[i]] + c[i]
            if n - 1 <= x and b[i] == n - 1:
                print('inf')
                exit(0)

print(d[n - 1] * -1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [None]*M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a-1, b-1, c)
d = [-float("inf") for _ in range(N)]
d[0] = 0

for i in range(N):
    for (f, t, c) in E:
        if d[f] != -float("inf") and d[t] < d[f] + c:
            d[t] = d[f] + c
            if i == N-1 and t == N-1:
                print("inf")
                exit()

print(d[-1])

Submission status: Accepted

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

N,M = map(int,input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])
    to[u].append(v)
    rto[v].append(u)

canVisitFromS = [False]*N
canVisitFromG = [False]*N

def dfs(u) :
    if canVisitFromS[u] : return
    canVisitFromS[u] = True
    for v in to[u] :
        dfs(v)

def rdfs(v) :
    if canVisitFromG[v] : return
    canVisitFromG[v] = True
    for u in rto[v] :
        rdfs(u)

dfs(0)
rdfs(N-1)

OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

update = True
step = 0
ans = 0

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 : continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    step += 1
    if step > N :
        ans = "inf"
        break
if ans != "inf" :
    ans = dist[N-1] * (-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print("inf" if ans1!=ans2 else -ans1)

Submission status: Accepted

Solution code:
from collections import deque

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

edges = []
dfsEdges = [[] for _ in range(N)]
dfsReverseEdges = [[] for _ in range(N)]

for _ in range(M):
    back, to, cost = map(int, input().split())
    back -= 1
    to -= 1
    edges.append((back, to, -cost))

    dfsEdges[back].append(to)
    dfsReverseEdges[to].append(back)

minDist = [float('inf') for _ in range(N)]
minDist[0] = 0

canGo = [False for _ in range(N)]
canBack = [False for _ in range(N)]

canGo[0] = True
canBack[N - 1] = True

def dfs(start, edge, confilm):
    que = deque([])
    que.append(start)

    while que:
        now = que.pop()
        for to in edge[now]:
            if not confilm[to]:
                que.append(to)
                confilm[to] = True

dfs(0, dfsEdges, canGo)
dfs(N - 1, dfsReverseEdges, canBack)

for time in range(N):
    for back, to, cost in edges:
        if minDist[to] > minDist[back] + cost:
            minDist[to] = minDist[back] + cost
            if time == N - 1:
                if canGo[to] and canBack[to]:
                    print('inf')
                    exit(0)

print(-minDist[N - 1])