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:
n,m=map(int,input().split())
E=[list(map(int,input().split())) for i in range(m)]
INF=float("inf")
dist=[INF]*n
dist[0]=0
for i in range(n):
  for fr,to,cost in E:
    fr,to=fr-1,to-1
    # スコアの正負を逆にしてスコアを最小化することを考える
    cost*=-1
    if dist[fr]!=INF and dist[to]>dist[fr]+cost:
      dist[to]=dist[fr]+cost
      # 負経路の存在チェック
      # 一番最後に緩和（更新）が発生するとNG（負閉路の長さは頂点の個数以下なので）
      if i==n-1 and to==n-1:
        print("inf")
        exit(0)
print(-dist[-1])

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
e1 = [[] for i in range(n)]
e2 = [[] for i in range(n)]
l = []
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    e1[a].append(b)
    e2[b].append(a)
    l.append([a,b,c])

def search(x,e):
    dis = [0]*n
    dis[x] = 1
    q = deque([])
    q.append(x)
    while q:
        now = q.popleft()
        for nex in e[now]:
            if dis[nex] == 0:
                dis[nex] = 1
                q.append(nex)

    return dis

dis1 = search(0,e1)
dis2 = search(n-1,e2)
dis = [0]*n
for i in range(n):
    if dis1[i] == 1 and dis2[i] == 1:
        dis[i] = 1

li = []
for i in range(m):
    a,b,c = l[i]
    if dis[a] == 1 and dis[b] == 1:
        li.append(l[i])

ans = [-float("INF")]*n
ans[0] = 0

for i in range(n):

    check = False
    for i,j,k in li:
        if ans[i]+k > ans[j]:
            ans[j] = ans[i]+k
            check = True
    
    if not check:
        print(ans[-1])
        exit()
print("inf")

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
e1 = [[] for i in range(n)]
e2 = [[] for i in range(n)]
l = []
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    e1[a].append(b)
    e2[b].append(a)
    l.append([a,b,c])

def search(x,e):
    dis = [0]*n
    dis[x] = 1
    q = deque([])
    q.append(x)
    while q:
        now = q.popleft()
        for nex in e[now]:
            if dis[nex] == 0:
                dis[nex] = 1
                q.append(nex)

    return dis

dis1 = search(0,e1)
dis2 = search(n-1,e2)
dis = [0]*n
for i in range(n):
    if dis1[i] == 1 and dis2[i] == 1:
        dis[i] = 1

li = []
for i in range(m):
    a,b,c = l[i]
    if dis[a] == 1 and dis[b] == 1:
        li.append(l[i])

ans = [-float("INF")]*n
ans[0] = 0

for i in range(2*n):

    check = False
    for i,j,k in li:
        if ans[i]+k > ans[j]:
            ans[j] = ans[i]+k
            check = True
    
    if not check:
        print(ans[-1])
        exit()
print("inf")

Submission status: Accepted

Solution code:
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    for _ in range(N):
        update = False
        for e in ed:
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d, True
    return 0, False

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(n):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i==n-1 and b==n-1:
                print('inf')
                exit()
print(dist[-1])

Submission status: Accepted

Solution code:
def Bellman_Ford(s, g, inf=1 << 60):
    # https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
    N = len(g)
    dist = [inf] * N
    dist[s] = 0

    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False

        if not_updated:
            return -dist[N - 1]

    # 負閉路が存在する
    ret = dist[N - 1]
    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False
        if not_updated: break

    if ret == dist[N - 1]:
        return -ret
    else:
        return 'inf'


def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, -c))

    ans = Bellman_Ford(s=0, g=g)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Bellman_Ford(s, g, inf=1 << 60):
    # https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
    N = len(g)
    dist = [inf] * N
    dist[s] = 0

    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False
        if not_updated: break

    else:
        # 負閉路が存在する
        ret = dist[N - 1]
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c

        if ret == dist[N - 1]:
            return -ret
        else:
            return 'inf'

    return -dist[N - 1]


def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, -c))

    ans = Bellman_Ford(s=0, g=g)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N-1):
        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]
    negative = [False] * N

    for i in range(N):
        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]
                negative[edge[1] - 1] = True
            if negative[edge[0] - 1] == True:
                negative[edge[1] - 1] =True
    
    return 'inf' if negative[-1] else -dist[-1]

print(bellman_ford(edges, N))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
NINF = -10**20
edge = []
dist = [NINF]*n
dist[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append((a-1, b-1, c))
for i in range(2*n):
    for a, b, c in edge:
        if dist[a]!=NINF and dist[b] < dist[a] + c:
            dist[b] = dist[a] + c
            if i>=n-1 and b==n-1:
                print('inf')
                exit()
print(dist[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
abc=[]
for i in range(m):
    a,b,c=map(int,input().split())
    abc.append([a-1,b-1,-c])
abc.sort()
INF=10**18
d=[INF]*n
chk=[False]*n
d[0]=0
for i in range(n-1):
    for a,b,c in abc:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
for i in range(n):
    for a,b,c in abc:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            chk[b]=True
            chk[a]=True
if chk[n-1]==True:
    print('inf')
else:
    print(-d[n-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split(' '))
piece=[0]*m
for i in range(m):
    piece[i]=tuple(map(int,input().split(' ')))

node=[0]+[float('inf')]*(n-1)

for v in range(n-1):
    for e in range(m):
        a,b,c=piece[e]
        if node[b-1] > node[a-1]-c:
            node[b-1] = node[a-1]-c
ans=node[n-1]
for e in range(m):
    a,b,c=piece[e]
    if node[b-1] > node[a-1] - c:
        node[b-1] = node[a-1] -c

if ans != node[n-1]:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
score = [inf] * (N + 1)
score[1] = 0

for _ in range(N - 1):
    for a, b, c in edge:
        score[b] = min(score[b], score[a] + c)

goal = score[N]
for a, b, c in edge:
    score[b] = min(score[b], score[a] + c)


if goal != score[N]:
    print("inf")
else:
    print(-goal)

Submission status: Accepted

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

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

def canGo():
    st = [N - 1]
    visited = [False] * N
    visited[N - 1] = True
    while st:
        for to in E[st.pop()]:
            if visited[to]:
                continue
            visited[to] = True
            st.append(to)
    return visited

V = canGo()

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

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N and V[to]:
                print('inf')
                exit()
            minDist[to] = d

print(-minDist[N - 1])

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-1, b-1, -c])

d = [float("inf") for _ in range(n)]
d[0] = 0

check = [0 for _ in range(n)]

for i in range(n):
    for now, next, weight in edge:
        if d[next] > d[now] + weight:
            d[next] = d[now] + weight
            if i == n-1:
                check[next] = 1
        if i == n-1:
            if check[now]:
                check[next] = 1

if check[-1]:
    print("inf")
else:
    print(-d[-1])

Submission status: Accepted

Solution code:
#負の経路の検出
def find_negative_loop(n, es, d):
    #始点はどこでもよい
    check = [0 for _ in range(n)]
    for _ in range(n):
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                check[q] = True
            if check[p]:
                check[q] = True
                # if i == n-1:
                #     return True
    return check

def shortest_path(s, n, es):
    #s -> i　の最短経路
    #s: 始点、n: 頂点数、w:辺の数、es[i]: [辺の始点、辺の終点、辺のコスト]
    d = [float("inf")] * n
    #d[i]: s->iの最短距離
    d[s] = 0
    for _ in range(n):
        update = False
        for p, q, r in es:
            #e: 辺iについて
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        # print(update)
        if not update:
            break
    return d

n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]

for _ in range(w):
    x,y,z = map(int,input().split())
    es.append([x-1, y-1, -z])
    # es.append([y,x,z])

# print(shortest_path(0, n, es))
# print(es)

# if find_negative_loop(n,es):

d = shortest_path(0, n, es)

# print(d)

c = find_negative_loop(n, es, d)
# print(c)



if c[-1]:
    print("inf")
else:
    # d = shortest_path(0, n, es)
    print(-d[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph=[[] for i in range(N+1)]
for _ in range(M):
    a,b,weight=map(int,input().split())
    graph[a].append((b,-weight))
    
class Node():
    def __init__(self,name):
        self.name=name
        self.par=None
        self.d=float("inf")
        
    def relax(self,other,weight):
        if self.d>other.d+weight:
            self.d=other.d+weight
            self.par=other.name
    def relax_(self,other,weight):
         if self.d>other.d+weight:
            self.d=other.d+weight
            return True
         return False
def bellman_ford(graph,s_node):
    N=len(graph)-1
    d_list=[Node(i) for i in range(N+1)]
    #初期化
    d_list[s_node].d=0
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)
    negative=[False for i in range(N+1)]
    for _ in range(N-1):
        #N回同じループを繰り返す
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                if d_list[point].relax_(d_list[node],distance):
                    if negative[point]==False:
                        negative[point]=True
                    else:
                        for que in graph[point]:
                            negative[que[0]]=True
    if negative[N]:
        return False

    return d_list[N].d

K=bellman_ford(graph,1)
if K!=False:
    print(-K)
else:
    print("inf")

Submission status: Accepted

Solution code:
'''
ベルマンフォード法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
負の辺が使われている場合に使う。
負のループがどこかにあればそれだけで検出する。

O(|E||V|)
'''
class BellmanFord():
    def __init__(self, N):
        '''
        Parameters
        ----------
        N:int
            the number of nodes
        '''
        self.N = N
        self.edges = []
    
    def add(self, u, v, d, directed=False):
        '''
        Parameters
        ----------
        u:int
            from node (not 0-index)
        v:int
            to node (not 0-index)
        d:int
            cost
        directed:bool
            there is direction
        '''
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def calc(self, s):
        '''
        Parameters
        ----------
        s:int
            start index (not 0-index)
        
        Returns
        ----------
        list or bool
            d[i] is shortest distances from node[s] to node[i]
            if there is negative loop, return False
        '''
        dist = [float('inf') for i in range(self.N)]
        dist[s-1] = 0
        #辺の緩和
        for i in range(self.N):
            for edge in self.edges:
                frm, to, cost = edge[0] - 1, edge[1] - 1, edge[2]
                # dist[frm]!=inf ->sから到達可能を意味する
                if dist[frm] != float('inf') and dist[to] > dist[frm] + cost:
                    dist[to] = dist[frm] + cost
                    # どこに負のループがあっても検出する
                    # if i == self.N - 1: return False
                    # 頂点Nに行く際に負のループがあるときだけ検出する
                    if i == self.N - 1 and to==self.N-1: return False
        return dist[-1]

'''
ABC061-D
N頂点M辺の重み付き有向グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
その辺を移動したときスコアc_iが加算される。
頂点1から始まり、頂点Nに駒があるときゲームを終了できる。
頂点1からNまで移動できることは保証されている。
ゲーム終了時のスコアを最大にするような行動をとった時の最大スコアを出力せよ。
スコアが無限に大きくなる場合はinfを出力せよ。

term:
2<=N<=1000
1<=M<=min(N(N-1),2000)
1<=a_i,b_i<=N
-10**9<=c_i<=10**9

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

output:
    7
'''

from collections import defaultdict,deque
import sys, bisect, math, itertools, heapq
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
graph=BellmanFord(n)
for _ in range(m):
    a, b, c = inpl()
    graph.add(a, b, -c, directed=True)  #\sum c_iを最大化する
result = graph.calc(1)
if result:
    print(-result)
else:
    print("inf")

'''
負になる閉路に頂点Nが入っていなければその閉路を経由して頂点Nにたどりつけない。
'''

Submission status: Accepted

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

renew=[0]*(n+1)
INF=float('inf')
def bellmanford(s,n):
    d = [INF for i in range(n+1)]
    d[s]=0
    q=[s]
    while q:
        x=q.pop()
        dist=d[x]
        for v,cost in edge[x]:
                if d[v]>dist+cost:
                    d[v]=dist+cost
                    q.append(v)
                    renew[v]+=1
                    if renew[v]>n:
                        d[v]=-INF
    return d
d=bellmanford(1,n)
print(-d[n])

Submission status: Accepted

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

renew=set()
from heapq import *
INF=float('inf')
def dijkstra(s,n):
    d = [INF for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            if (u,v) in renew:
                d[v]=-INF
            renew.add((u,v))
            heappush(pq,(d[v],v))
    return d             
d=dijkstra(1,n)
print(-d[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
check=[False for i in range(n+1)]
inf=False
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n-1):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      check[e]=True
    if check[s]:
      check[e]=True
if check[-1]:
  print('inf')
else:
  print(-node[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
node=[-float('inf') for i in range(n+1)]
node[1]=0
inf=False
for i in range(2*n+1):
  loop=False
  for s,e,c in edge:
    if node[e]<node[s]+c:
      node[e]=node[s]+c
      if e==n:
        loop=True
  if i>=n and loop:
    inf=True
    break
if inf:
  print('inf')
else:
  print(node[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
node=[-float('inf') for i in range(n+1)]
node[1]=0
inf=False
for i in range(2*n+1):
  change=False
  for s,e,c in edge:
    if node[e]<node[s]+c:
      node[e]=node[s]+c
      if e==n:
        change=True
  if i>=n and change:
    inf=True
if inf:
  print('inf')
else:
  print(node[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[a] and reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[False]*(N+1)
for i in range(1,N+1):
  if not reachable[i]:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:        
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])