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:
class Graph():  #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.deg[e[1] - indexed] += 1

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

    def bellman_ford(self, s, t=None, INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        update = True
        for i in range(self.n):
            update = False
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        update = True
            if not update:
                return dist[t] if t is not None else dist
        if t is None:
            return
        negative_cycle = [0 for _ in range(self.n)]
        for i in range(self.n):
            for node, g in enumerate(self.graph):
                for adj, adjcost in g:
                    if dist[node] != INF and dist[node] + adjcost < dist[adj]:
                        dist[adj] = dist[node] + adjcost
                        negative_cycle[adj] = True
        if not negative_cycle[t]:
            return dist[t]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = []

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

g = Graph(N, E)
bf = g.bellman_ford(0, N - 1)

print(-bf if bf is not None else 'inf')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#g=[[]for _ in range(n)]
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[a-1,b-1,-c] for a,b,c in abc]
# BellmanFord
# ベルマンフォード法
def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source]=0  
  #辺の緩和
  for i in range(num_v):
    for edge in edges:
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        #if i==num_v-1: return -1
  negative=[False]*n
  for i in range(num_v):
    for edge in edges:
      if negative[edge[0]]:negative[edge[1]]=True
      if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
        negative[edge[1]] = True
  return dist[n-1],negative[n-1]
c,d=BellmanFord(abc,n,0)
# 負の閉路にNが含まれない時はinfじゃない
if d:
  print('inf')
else:
  print(-c)

Submission status: Accepted

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

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    # 注意点として、閉路を探索(=スコアが更新されたか確かめる)ためにn*2回実行する必要がある
    for i in range(n*2):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i>=n-1 and edge[1] == n-1:
                    return -1
    return d

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

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for e in es:
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if e.to == N-1 and i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    for _ in range(N-1):
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print(-d[N-1])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    
score = [None]*n
score[0] = 0
prev = score
for i in range(n+3):
    update = False
    for u in range(n):
        if prev[u] is not None:
            for c,v in ns[u]:
                if score[v] is None or score[v]<prev[u]+c:
                    score[v] = prev[u]+c
                    update = True
    if not update:
        print(score[-1])
        break
    prev = score
else:
    reach = [False]*n
    for i in range(n+1):
        for u in range(n):
            if prev[u] is not None:
                for c,v in ns[u]:
                    if score[v] is None or score[v]<prev[u]+c:
                        score[v] = prev[u]+c
                        reach[v] = True
    if reach[-1]:
        print("inf")
    else:
        print(score[-1])

Submission status: Accepted

Solution code:
def bellman_ford(s):
    d = [float('inf')]*(N+1) # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    nega = [0 for i in range(N+1)]
    for i in range(N+1):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
                nega[y] += 1
        if not update:
            break
        # 負閉路が存在
        if i == N :
          d[0] = -1
    return [d,nega]

N,M = map(int,input().split())
g = []

for _ in range(M):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, -z])

ans = bellman_ford(1)

if ans[1][-1] > 1:
  print("inf")
else:
  print(int(-ans[0][-1]))

Submission status: Accepted

Solution code:
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        e=0
        for x, y, z in g:
            if d[y] > d[x] + z and d[x] != float('inf'):
                d[y] = d[x] + z
                e+=1
        # 負閉路が存在
                if i == n - 1 and y==n-1 :
                 return "inf"
    return (-1)*d[n-1]

n, m = map(int,input().split()) # n:頂点数, w:辺の数
g = []
for k in range(m):
    a, b, c = map(int,input().split()) # 始点,終点,コスト
    g.append([a-1, b-1, -c])
print(bellman_ford(0))

Submission status: Accepted

Solution code:
import queue
def bfs(G, s):
    st = set()
    q = queue.Queue()
    st.add(s)
    q.put(s)
    while not q.empty():
        p = q.get()
        for v, _ in G[p]:
            if not v in st:
                st.add(v)
                q.put(v)
    return st

def solve(G, st):
    n = len(G)
    score = [-float("inf")]*n
    score[0] = 0
    for i in range(n):
        f = True
        for s in range(n):
            for t, u in G[s]:
                if not s in st or not t in st:
                    continue
                if score[t] < score[s] + u:
                    f = False
                    score[t] = score[s] + u
        if f:
            break
        if i == n-1:
            return "inf"
    return score[n-1]

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n)]
    revG = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        a, b = a-1, b-1
        G[a].append([b, c])
        revG[b].append([a, c])
    st1 = bfs(G, 0)
    st2 = bfs(revG, n-1)
    st = st1 & st2
    print(solve(G, st))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(V,E,r,edges):
    cost=[-float('inf')]*V
    cost[r]=0
    for _ in range(V-1):
        for edge in edges:
            s=edge[0]
            t=edge[1]
            d=edge[2]
            if cost[t]<cost[s]+d:
                cost[t]=cost[s]+d
    ans=cost[V-1]
    for _ in range(V-1):
        for edge in edges:
            s=edge[0]
            t=edge[1]
            d=edge[2]
            if cost[t]<cost[s]+d:
                cost[t]=cost[s]+d
    if ans!=cost[V-1]:
        return float('inf')
    return ans
            



V,E=map(int,input().split())
edges=[]
for _ in range(E):
    s,t,d=map(int,input().split())
    s-=1
    t-=1
    edges.append(tuple((s,t,d)))
ans=solve(V,E,0,edges)
if ans==float('inf'):
    print("inf")
else:
    print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(m)]
dist = [-float("inf")]*(n+1)
dist[1] = 0
for i in range(n):
  for a, b, c in ABC:
    if dist[b] < dist[a]+c:
      if i == n-1 and b == n:
        print("inf")
        exit()
      dist[b] = dist[a]+c
ans = dist[n]
print(ans)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford, connected_components
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline


N, M = map(int, input().split())
starts = []
ends = []
costs = []
for _ in range(M):
    a, b, c = map(int, input().split())
    starts.append(a-1)
    ends.append(b-1)
    if c != 0:
        costs.append(-c)
    else:
        costs.append(sys.float_info.epsilon)

look_for_loop = csr_matrix((costs + [0], (starts + [N-1], ends + [0])), shape = (N, N))
_, labels = connected_components(look_for_loop, connection = "strong")
mask = (labels == labels[0])

graph = csr_matrix((costs, (starts, ends)), shape = (N, N)).toarray()
graph = graph[mask, :][:, mask]

try:
    ans = bellman_ford(graph, directed = True, indices = [0])[0][-1]
    ans = int(round(-ans))
except NegativeCycleError:
    ans = "inf"

print(ans)

Submission status: Accepted

Solution code:
import sys
from _collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def Bellmanford(n, edges, r):  # r: 始点
    d = [INF] * n
    d[r] = 0

    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n - 1 and v == n - 1:
                    return 'inf'

    return -d[n - 1]

def main():
    N, M = map(int, readline().split())
    edges = []
    for _ in range(M):
        u,v,c = map(int, readline().split())
        edges.append([u-1,v-1,-c])

    d = [INF]*N
    d[0] = 0
    for i in range(N-1):
        for j in range(M):
            u, v, c = edges[j]
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
    ans = d[N-1]

    negative_loop = [False]*N
    for i in range(N):
        for j in range(M):
            u, v, c = edges[j]
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                negative_loop[v] = True
            if negative_loop[u]==True:
                negative_loop[v]=True

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




if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Bellman_Ford(S,V,E,distance):
    min_distance = [float("inf")]*V # min_distance[i] は始点から街iまでの最短距離
    min_distance[S-1] = 0 # 始点から始点への最短距離は0とする
    count = 1
    while count < 2*V:
        if count == V:
            tmp = min_distance[N-1]
        count += 1
        for s,g,d in distance: # [s,g,d] = [道路の始点,道路の終点,道路の長さ] について、すべての道路を見る
            if min_distance[s] != float("inf") and min_distance[s] + d < min_distance[g]: # 最短経路が確立されている街から伸びる道路を通ることで、距離を短くできるならば、
                min_distance[g] = min_distance[s] + d # 最短距離を上書きする
    return min_distance,tmp

min_distance,ansN = Bellman_Ford(1,N,M,line)
ans2N = min_distance[N-1]
if ansN == ans2N:
    print(-ansN)
else:
    print("inf")

Submission status: Accepted

Solution code:
import sys
INF = float("inf")


def Bellmanford(n, edges, r):  # rは始点
    d = [INF] * n
    d[r] = 0

    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n - 1 and v == n - 1:
                    return "inf"
    return -d[n-1]


N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M
for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai - 1, bi - 1, -ci)

ans = Bellmanford(N, Edges, 0)
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    root = []
    for _ in range(M):
        a,b,c = LI()
        root.append((a-1,b-1,c))
    node = [-INF]* N

    node[0] = 0
    up = False
    for _ in range(N):
        up = False
        for a,b,c in root:
            if node[a] + c > node[b]:
                node[b] = node[a] + c
                if b == N-1: up = True
    if up:
        print('inf')
    else:
        print(node[N-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cost = [-float('inf')]*N
cost[0] = 0

for i in range(2):
    for a,b,c in abc:
        a,b = a-1,b-1
        cost[b] = max(cost[b], cost[a] + c)

    if i == 0:
        ans = cost[N-1]
    else:
        Max = cost[N-1]


if ans != Max:
    print('inf')
else:
    print(ans)

Submission status: Accepted

Solution code:
n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

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

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1:
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

Submission status: Accepted

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

cost = [-float('inf')]*N
cost[0] = 0

for i in range(N):
    update = False
    for a,b,c in abc:
        a,b = a-1,b-1
        if cost[a] != -(10**10)*N:
            if cost[b] < cost[a] + c:
                cost[b] = cost[a] + c
                update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])


if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)

Submission status: Accepted

Solution code:
n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

INF = 10 ** 13
cost = [ INF ] * n
cost[ 0 ] = 0

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1:
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

Submission status: Accepted

Solution code:
n, m = map( int, input().split() )
edge_list = []
for _ in range( m ):
    a_i, b_i, c_i = map( int, input().split() )
    edge_list.append( ( a_i - 1, b_i - 1, - c_i ) )

INF = 10 ** 15
cost = [ INF ] * n
cost[ 0 ] = 0

NegativeLoopExist = False
for i in range( n ):
    for j in range( m ):
        a, b, c = edge_list[ j ]
        if cost[ a ] != INF and cost[ b ] > cost[ a ] + c:
            cost[ b ] = cost[ a ] + c
            if i == n - 1 and b == n - 1 :
                NegativeLoopExist = True

if NegativeLoopExist:
    print( "inf" )
else:
    print( - cost[ n - 1 ] )

Submission status: Accepted

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

cost = [-(10**10)*N]*N
cost[0] = 0

for i in range(N):
    update = False
    for a,b,c in abc:
        a,b = a-1,b-1
        if cost[a] != -(10**10)*N:
            if cost[b] < cost[a] + c:
                cost[b] = cost[a] + c
                update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])


if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

from collections import deque
ls = [deque([]) for _ in range(N)]

for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    ls[a].append([b,c])
cost = [-(10**10)*N]*N
cost[0] = 0

for i in range(N):
    update = False
    q = [deque(m for m in l) for l in ls]
    for j in range(N):
        if cost[j] != -(10**10)*N:
            while q[j]:
                b,c = q[j].pop()
                if cost[b] < cost[j] + c:
                    cost[b] = cost[j] + c
                    update = True
    if i == 0:
        Max = cost[N-1]
    elif i < N-1:
        Max = max(Max,cost[N-1])

if update == True and Max < cost[N-1]:
    print('inf')
else:
    print(Max)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
NMAX = 1000; MMAX = 2000

INF = 10**15

edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    # 最短距離の問題に変える
    a -= 1; b -= 1; c = -c
    edge.append([a, b, c])

# Bellman-Ford O(NM)
dist = [INF for _ in range(NMAX)] # 頂点1からの最短距離を格納する配列
dist[0] = 0
for loop in range(n):
    for i in range(m):
        a, b, c = edge[i]
        if dist[a] == INF:
            continue
        dist[b] = min(dist[b], dist[a]+c)

ans = dist[n-1]

# 負の閉路検出 O(NM)
## すでにBellman-Fordを実施しているので、distには頂点1から各頂点vまでの最短距離が格納されているはず
## もしまだ更新されるようなら、負の閉路(問題に合わせると正の閉路)が存在していることになる
negative = [False for _ in range(NMAX)] # 頂点iが負の閉路に含まれる場合はTrue
for loop in range(n):
    for i in range(m):
        a, b, c = edge[i]
        if dist[a] == INF:
            continue
        if dist[b] > dist[a]+c:
            dist[b] = dist[a]+c
            negative[b] = True
        if negative[a]:
            negative[b] = True

if negative[n-1]:
    print("inf")
else:
    print(-ans)

Submission status: Accepted

Solution code:
def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V: int, es: list, source=0):
	INF = float("inf")
	D = [INF] * V
	D[source] = 0
	for _ in range(V):
		upd = False
		for f, t, c in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		# Negative Cycle
		return None


def main():
	N, M, *L = map(int, open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = []
	for a, b, c in zip(*[iter(L)] * 3):
		fwd[a - 1].append(b - 1)
		bwd[b - 1].append(a - 1)
		tmp += [(a - 1, b - 1, - c)]
	ra = reachable(fwd, 0) & reachable(bwd, N - 1)
	ans = BellmanFord(N, [(a, b, c) for a, b, c in tmp if a in ra and b in ra])
	if ans == None:
		print("inf")
	else:
		print(-ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
edges = []
for _ in range(M):
  u,v,c = map(int, input().split())
  edges.append((-c,u-1,v-1))

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for _ in range(N-1):
  for c,u,v in edges:
    if dist[v] > c+dist[u]:
      dist[v] = c+dist[u]

neg_cycle = [False]*N
for c,u,v in edges:
  if dist[v] > c+dist[u]:
    dist[v] = c+dist[u]
    neg_cycle[u] = True
    neg_cycle[v] = True

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


def bellman_ford(edges, num_v, sv):
    #グラフの初期化
    dist = [INF] * num_v
    dist[sv] = 0
    
    #辺の緩和
    for i in range(num_v - 1):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] != INF and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
    
    return dist


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

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

    negative = [False]*N
    for _ in range(N):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] == INF:
                continue
            if dist[t] > dist[s] + d:
                dist[s] = dist[t] + d
                negative[t] = True
            if negative[s] == True:
                negative[t] = True

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[]
    for i in range(M):
        a,b,c=map(int1,input().split())
        c+=1
        edge.append((a,b,-c))
    d=[INF]*N
    d[0]=0
    f=False
    for i in range(N*2):
        for a,b,c in edge:
            if d[b]>d[a]+c:
                if i<N-1:
                    d[b]=d[a]+c
                else:
                    if d[a]<10**17:
                        d[b]=-INF
                    if b==N-1:
                        f=True
    if f:
        print('inf')
    else:
        print(-d[N-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def BellmanFord():
    def BF(s, n, edge, inf=float("inf")):
        d = [inf for i in range(n)]
        d[s] = 0
        for i in range(n):
            for before, after, dist in edge:
                if before != inf:
                    d[after] = min(d[after], d[before] + dist)
            if i == n - 2:
                t = d[:]
            elif i == n - 1:
                for i, j in enumerate(d):
                    if j != t[i]:
                        d[i] = -inf
        return list(map(lambda x: -x, d))
    n, m = map(int, input().split())
    inf = 10 ** 20
    edge = [list(map(int, input().split())) for i in range(m)]
    edge = [[x - 1, y - 1, -z] for x, y, z in edge]
    l = BF(0, n, edge)
    print(l[-1] if l[-1] < inf else "inf")
BellmanFord()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

can_reach_from_start = [False] * N
can_reach_from_goal = [False] * N
def dfs(i,reach,Gragh):
    for e in Gragh[i]:
        if reach[e]:
            continue
        reach[e] = True
        dfs(e,reach,Gragh)

can_reach_from_start[0] = True
dfs(0,can_reach_from_start,G)
can_reach_from_goal[-1] = True
dfs(N - 1,can_reach_from_goal,G_inv)

X = 0
for i in range(N):
    if can_reach_from_goal[i] and can_reach_from_start[i]:
        X += 1

new_edge = []
for a,b,c in edge:
    if can_reach_from_start[a] and can_reach_from_goal[b]:
        new_edge.append((a,b,c))

def beruman(N,edges,start = 0,negative_loop = False):
    find_negative = False #startを含む負の閉路が存在するか
    dist = [INF] * N
    dist[start] = 0

    for i in range(X):
        update = False
        for a,b,c in edges:
            if dist[a] != INF and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                update = True

        if not update:
            break
        if i == X - 1:
            find_negative = True
    
    if negative_loop:
        return dist,find_negative
    else:
        return dist

dist,judge = beruman(N,new_edge,0,True)
if judge:
    print('inf')
else:
    print(-dist[-1])

Submission status: Accepted

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        if i != self.N - 1:
                            d[v] = d[u] + c
                        else:
                            d[v] = -float('inf')
                            for i in range(self.N):
                                for u in self.e.keys():
                                    for v, c in self.e[u]:
                                        if d[v] > d[u] + c:
                                            d[v] = d[u] + c
                            if d[N] == -float('inf'):
                                return True,d
                            else:
                                return False,d
        return False,d

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

bool,d = G.BellmanFord_negative_bool(1)
if bool:
    print('inf')
    exit()

print(-d[N])

Submission status: Accepted

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

INF = 10**15
d = [INF] * N
d[0] = 0
def bellman_ford():
  global d
  for i in range(N):
    for a, b, c in road:
      d[b] = min(d[b], d[a] + c)

bellman_ford()
for a, b, c in road:
  new_d = d[a] + c
  if new_d < d[b]:
    d[b] = - float('inf')

bellman_ford()
if d[-1] > -float('inf'):
  print(int(-d[-1]))
else:
  print('inf')

Submission status: Accepted

Solution code:
N,M,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
rdic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append(b)
  rdic[b].append(a)

ok1 = [False]*(N+1)
ok1[1] = True
q = [1]
while q:
  p = q.pop()
  for v in dic[p]:
    if not ok1[v]:
      ok1[v] = True
      q.append(v)
ok2 = [False]*(N+1)
ok2[N] = True
q = [N]
while q:
  p = q.pop()
  for v in rdic[p]:
    if not ok2[v]:
      ok2[v] = True
      q.append(v)
ok = [a&b for a,b in zip(ok1,ok2)]
cnt = 0
dist = [-10**20]*(N+1)
dist[1] = 0
while True:
  flag = True
  for a,b,c in zip(*[iter(L)]*3):
    if ok[a]&ok[b] and ok[a]!=-10**20 and dist[b]<dist[a]+c:
      flag = False
      dist[b] = dist[a]+c
  if flag:
    print(dist[N])
    break
  cnt += 1
  if cnt>N:
    print('inf')
    break

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
inf = 10**18
edges = []

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

dist = [inf]*N
dist[0] = 0
update = False
for i in range(N):
    for a, b, c in edges:
        if dist[b]>dist[a]+c:
            dist[b] = dist[a]+c
            if b==N-1 and i==N-1:
                update = True

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