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:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for _ in range(N+1) ]   #隣接リスト
rev_al=[ [] for _ in range(N+1) ]   #戻りを調べる用の隣接リスト
edge=[] #辺の集合
for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    al[a].append(b)
    rev_al[b].append(a) #逆向きにも辺を張る
    edge.append((a,b,c))


go=[0 for _ in range(N+1)]
back=[0 for _ in range(N+1)]

#頂点１からNに行くまでに使用する頂点を調べる
q=deque()
q.append(1) #スタート地点
go[1]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if go[to]==0:
            go[to]=1
            q.append(to)


#頂点Nから1に戻る際に使用する頂点を調べる
q=deque()
q.append(N) #スタート地点
back[N]=1

while q:
    fro=q.popleft()
    for to in rev_al[fro]:
        if back[to]==0:
            back[to]=1
            q.append(to)


new_edge=[]     #有効な辺のみ抽出

for a,b,c in edge:
    if go[a]==1 and back[b]==1:
        new_edge.append((a,b,c))


#ベルマンフォード
dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in new_edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N-1:
                print float("inf")
                quit()
            dp[to]=alt

print dp[N]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
#edge=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]   #辺
al=[ [] for _ in range(N+1) ]   #隣接リスト
rev_al=[ [] for _ in range(N+1) ]   #戻りを調べる用の隣接リスト
edge=[] #辺の集合
for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    al[a].append(b)
    rev_al[b].append(a) #逆向きにも辺を張る
    edge.append((a,b,c))


go=[0 for _ in range(N+1)]
back=[0 for _ in range(N+1)]

#頂点１からNに行くまでに使用する頂点を調べる
q=deque()
q.append(1) #スタート地点
go[1]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if go[to]==0:
            go[to]=1
            q.append(to)


#頂点Nから1に戻る際に使用する頂点を調べる
q=deque()
q.append(N) #スタート地点
back[N]=1

while q:
    fro=q.popleft()
    for to in rev_al[fro]:
        if back[to]==0:
            back[to]=1
            q.append(to)


new_edge=[]     #有効な辺のみ抽出

for a,b,c in edge:
    if go[a]==1 and back[b]==1:
        new_edge.append((a,b,c))


#ベルマンフォード
dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in new_edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N-1:
                print float("inf")
                quit()
            dp[to]=alt

print dp[N]

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
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
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)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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


def bellman_ford(G, start=0):
    n = len(G)
    costs = [-INF] * n
    costs[0] = 0
    v_nows = set([start])
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if costs[u] + c > costs[v]:
                    costs[v] = costs[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return costs[n - 1]

    for i in v_nows:
        costs[i] = INF
    que = deque(v_nows)
    while que:
        u = que.popleft()
        for v, _ in G[u]:
            if costs[v] != INF:
                costs[v] = INF
                que += [v]
    return costs[n - 1]


cost = bellman_ford(G, 0)
if cost == INF:
    print('inf')
else:
    print(cost)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
d = [-float('inf')]*(n+1)
d[1] = 0
for _ in range(n):
    for i,j,c in e:
        d[j] = max(d[j], d[i]+c)
t = d[n]
for _ in range(n):
    for i,j,c in e:
        d[j] = max(d[j], d[i]+c)

if t < d[n]:
    print('inf')
else:
    print(d[n])

Submission status: Accepted

Solution code:
inf=10**43
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)
d=[inf]*n 
f=1 
d[0]=0 
for i in range(n-1): 
    for (a,b,c) in edges: 
        if d[a]+c<d[b]:
            d[b]=d[a]+c #update distances 
#print(d)
for i in range(n):
    for (a,b,c) in edges: 
        if d[b]>d[a]+c:  #how can a->b be minimised by travelling 
                         #some other path
            if b==n-1:
                f=0
                #print(b,d[b])
            else:
                d[b]=d[a]+c 
if f:  
    print(-d[n-1])
else:
    print('inf')

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:
import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c])
inf=10**30
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==N and y==N-1:
            print('inf')
            sys.exit()
print(-dist[N-1])

Submission status: Accepted

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うためスコアと重みはマイナスの値

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place]: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Submission status: Accepted

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うためスコアと重みはマイナスの値

def dijkstra(start, co):
    INF = 10 ** 15
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-d1[N])

Submission status: Accepted

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2 and count < 2000: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))

Submission status: Accepted

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

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))
edges.sort()

def bellmanford(n, edges, start):
    INF = float('inf')
    dist = [-INF] * (n+1) # dist[0]は使わない
    dist[start] = 0

    for i in range(n):
        for (pre, ne, weight) in edges:
            if dist[pre] != -INF and dist[pre] + weight > dist[ne]:
                dist[ne] = dist[pre] + weight
                if i == n-1 and ne == n:
                    return 'inf'
    return dist[n]

answer = bellmanford(N, edges, 1)
print(answer)

Submission status: Accepted

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

list_point = [float("inf") if i != 0 else 0 for i in range(n)]
for i in range(n+1):
  for a, b, c in list_edge:
    if list_point[a] != float("Inf") and list_point[b] > list_point[a] + c:
      list_point[b] = list_point[a] + c
      if i == n and b == n-1:
        print("inf")
        exit()
print(-1 * list_point[-1])

Submission status: Accepted

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

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Accepted

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

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

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

def dijkstra(start, c):
    INF = float('inf')
    dist = [-INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(start, 0, c)]
    while que:
        place, score, count = heappop(que) # placeは現在地
        if score < dist[place] or count > 3000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] < score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (next_node, score2, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(d1[N]))

Submission status: Accepted

Solution code:
# ABC61 D - Score Attack  preference付

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,n,d):
    cost       = [-float("inf")]*(n+1)
    preference = [None         ]*(n+1)      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for nownode,nextnode,c in d:
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode

    negative=[0]*(n+1)                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for nownode,nextnode,c in d:
            if negative[nownode]:
                negative[nextnode]=1
            if cost[nextnode]<cost[nownode]+c:
                cost[nextnode]=cost[nownode]+c
                preference[nextnode]=nownode
                negative[nownode]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d=[tuple(map(int,input().split()))for i in [0]*m]
    
    x,y=(BELLMANFORD(1,n,d))
    
    if y[n]:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  #infが定数なので論理が逆
                cost[nextnode]=cost[nownode]+c
    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n]


def main():
    n,m=map(int,input().split())
    
    d=[]
    for i in range(m):
        a,b,c=map(int,input().split())
        d.append((a,b,-c))
    
    print(BELLMANFORD(1,n,d))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,d,n):
    cost       = [-float("inf")for node in range(n+1)]
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n))
    
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,d,n):
    cost       = [-float("inf")for node in range(n+1)]
    preference = [None         for node in range(n+1)]      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    
    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n))
    
    if y[n-1]>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bellman_ford(V, E, s, std):
  dist = [float('inf') for _ in range(V)]
  dist[s] = 0
  for i in range(V):
    for s, t, d in std:
      s -=1
      t -= 1
      d = -d
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if i == V-1 and t+1 == V:
          return -1 
  return dist

def main():
  N, M = map(int, input().split())
  abc = [list(map(int, input().split())) for _ in range(M)]
  dist = bellman_ford(N, M, 0, abc)
  if dist == -1:
    print('inf')
    exit()
  else:
    print(-dist[N-1])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[list(map(int, input().split()))for _ in range(m)]
inf=float("inf")
d=[inf]*(n+1)
d[1]=0
for _ in range(n):
    for a,b,c in e:d[b]=min(d[b],d[a]-c)
x=d[n]
for a,b,c in e:d[b]=min(d[b],d[a]-c)
if x!=d[n]:print(inf)
else:print(-x)

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

    for _ in range(N - 1):
        for a, b, c in E:
            if D[a] == INF:
                continue
            D[b] = min(D[b], D[a] + c)

    ans = D[-1]
    neg = [False] * N

    for _ in range(N):
        for a, b, c in E:
            if D[a] == INF:
                continue

            if D[b] > D[a] + c:
                D[b] = D[a] + c
                neg[b] = True

            if neg[a]:
                neg[b] = True

    print("inf" if ans != D[-1] else -ans)

main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = tuple((a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    print("inf" if ans != D[-1] else -ans)

main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [0] + [INF] * (N - 1)
    E = [(a - 1, b - 1, -c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] + c)

    print("inf" if ans != D[-1] else -ans)

main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [INF, 0] + [INF] * (N - 1)
    E = tuple(zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    print("inf" if ans != D[-1] else -ans)

main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

    N, M, *ABC = map(int, open(0).read().split())

    D = [INF, 0] + [INF] * (N - 1)
    E = tuple(zip(*[iter(ABC)] * 3))

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    ans = D[-1]

    for a, b, c in E:
        D[b] = min(D[b], D[a] - c)

    print("inf" if ans != D[-1] else -ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = float("inf")

N, M, *ABC = map(int, open(0).read().split())

D = [INF, 0] + [INF] * (N - 1)
E = tuple(zip(*[iter(ABC)] * 3))

for a, b, c in E:
    D[b] = min(D[b], D[a] - c)

ans = D[-1]

for a, b, c in E:
    D[b] = min(D[b], D[a] - c)

print("inf" if ans != D[-1] else -ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)

d = [INF]*n
d[0] = 0
for i in range(n-1):
    for e in E:
        if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
            d[e[1]] = d[e[0]]+e[2]
res =  d[n-1]

for e in E:
    if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
            d[e[1]] = d[e[0]]+e[2]




if  res != d[n-1]:
    print('inf')
else:
    print(res*-1)

Submission status: Accepted

Solution code:
from collections import deque


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

dic = {}

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []

    dic[a].append([b,c])

lis = [[0] * N for j in range(N)]
lis[0][0] = 1
lmax = [0] * N
lmax[0] = 1

mcost = [-1 * float("inf")] * N
mcost[0] = 0

q = deque([])
q.append(0)
cnt = 0

while len(q) > 0:

    now = q.pop()

    if now not in dic or lmax[now] > N:
        continue

    for npath in dic[now]:

        b = npath[0]
        c = npath[1]

        if mcost[now] + c > mcost[b]:
            mcost[b] = mcost[now] + c
            lis[b] = lis[now].copy()
            lmax[b] = lmax[now]
            lis[b][b] += 1
            lmax[b] = max(lmax[b],lis[b][b])

            if lmax[b] >= 2:
                mcost[b] = float("inf")
            q.append(b)

    if lis[N-1][N-1] != -1 * float("inf") and lmax[N-1] >= 2:
        mcost[N-1] = float("inf")
        break

    elif mcost[N-1] == float("inf"):
        break

print (mcost[N-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    
    N,M = map(int, input().split())
    G = [[] for i in range(N+2)]
    iG = [[] for i in range(N+2)]
    E = []
    for i in range(M):
        a,b,c = map(int,input().split())
        G[a].append([b,-c])
        iG[b].append([a,-c])
        E.append([a,b,c])
        
    from1 = [0]*(N+2)
    toN = [0]*(N+2)
    que = [1]
    while que != []:
        v = que.pop()
        from1[v] = 1
        for L in G[v]:
            b,c = L
            if from1[b] == 0:
                que.append(b)
    que = [N]
    while que != []:
        v = que.pop()
        toN[v] = 1
        for L in iG[v]:
            b,c = L
            if toN[b] == 0:
                que.append(b)
    
    oneN = [0]*(N+2)
    for i in range(N+1):
        oneN[i] = from1[i]*toN[i]
    
    
    itG =[[] for i in range(N+2)]
    for e in E:
        a,b,c = e
        if oneN[a]==oneN[b]==1:
            itG[b].append([a,-c])
            
    import copy
    cost = [float("inf")]*(N+2)
    cost[1] = 0
    for i in range(N+2):
        tmpcost = copy.deepcopy(cost)
        for j in range(1,N+1):
            for e in itG[j]:
                a,c = e
                #print(j,a,c)
                tmpcost[j] = min(tmpcost[j], cost[a]+c)
                #print(tmpcost)
        #print(tmpcost)
        cost = copy.deepcopy(tmpcost)
    flag = 0
    tmpcost = copy.deepcopy(cost)
    for j in range(1,N+1):
        for e in itG[j]:
            a,c = e
            if cost[a]+c < cost[j]:
                #print(cost[a]+c)
                flag = 1
                break
    #print(from1)
    #print(toN)
    #print(oneN)
    #print(itG)
    #print(tmpcost)
    if flag == 1:
        print("inf")
    else:
        print(-cost[N])
    
    
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    dist=[float("inf")]*n
    dist[0]=0
    edges=[0]*m
    for i in range(m):
        a,b,c=map(int,input().split())
        edges[i]=[a-1,b-1,-c]

    # Bellman-Ford
    for k in range(1,2*n): # 2n-1回やって、n-1と2n-1のscoreを見る
        for u,v,cost in edges:
            if dist[v]>dist[u]+cost:
                dist[v]=dist[u]+cost
        if k==n-1:
            ans=dist[n-1]

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

resolve()

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


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

edge_list = []
for _ in range(M):
	a, b, c = list(map(int, input().split()))
	a -= 1
	b -= 1
	edge_list.append((a, b, c))
dist = [-(10**20) for _ in range(N)]
dist[0] = 0

for times in range(N):
	for edge in edge_list:
		if dist[edge[0]] > -(10**20):
			if dist[edge[1]] == -(10**20):
				dist[edge[1]] = dist[edge[0]] + edge[2]
			else:
				dist[edge[1]] = max(dist[edge[1]], dist[edge[0]] + edge[2])
score = dist[N - 1]

for times in range(N):
	for edge in edge_list:
		if dist[edge[0]] > -(10**20):
			if dist[edge[1]] == -(10**20):
				dist[edge[1]] = dist[edge[0]] + edge[2]
			else:
				dist[edge[1]] = max(dist[edge[1]], dist[edge[0]] + edge[2])

if score < dist[N - 1]:
	print("inf")
else:
	print(dist[N - 1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def belman(egdes, N, start, end):
    INF = int(1e18)
    cost = [INF] * N
    cost[start] = 0
    fin = False
    count = 0
    while True:
        no_change = True
        for edge in egdes:
            from_, to_, d = edge
            tmp = cost[from_] + d
            if cost[to_] > tmp:
                no_change = False
                cost[to_] = tmp
        count += 1
        if no_change:
            fin = True
            break
        elif count > N+1:
            break
    
    if fin:
        return -cost[end]
    else:
        return "inf"

def bfs(link, N, start):
    q = deque()
    check = [False] * N
    q.append(start)
    check[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for next_ in link[node]:
            if not check[next_]:
                check[next_] = True
                q.append(next_)
                used.add(next_)
    return used
        

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

    link = [[] for i in range(N)]
    rlink = [[] for i in range(N)]
    edges = []

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        link[a].append(b)
        rlink[b].append(a)
        edges.append((a, b, -c))
    
    use_nodes = bfs(link, N, 0) & bfs(rlink, N, N-1)
    use_edges = [(a, b, c) for a, b, c in edges if a in use_nodes and b in use_nodes]
    print(belman(use_edges, N, 0, N-1))

if __name__ == "__main__":
    main()

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]:
                        negative[b] = True
                        dist[b] = dist[a] + graph[a][b]
                    if negative[a] == True:
                        negative[b] = True

    if negative[N-1] == True:
        return "inf"
    else:
        return -ans


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