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())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])

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

for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()

print(-dist[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
big=10**13
data=[-1*float('inf')]*(N+1)
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
from collections import deque
check=deque()
check.append((1,0,set()))
data[1]=0
while len(check)>0:
    now=check.popleft()
    for b,c in branch[now[0]]:
        if now[1]+c>data[b]:
            if data[b]>big:continue
            if b in now[2]:
                data[b]=float('inf')
                check.append((now[0],float('inf'),now[2]|{now[0],b}))
                check.append((b,float('inf'),now[2]|{now[0],b}))
            else:
                data[b]=now[1]+c
                check.append((b,now[1]+c,now[2]|{now[0],}))
if data[N]>big:print('inf')
else:print(data[N])

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    for j in range(M):
        is_updated = False
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edges = []
for _ in range(M):
    a,b,c = map(int,input().split())
    edges.append((a,b,-c))
INF = 10**9*M*10*2
d = [INF for _ in range(N+1)]
d[1] = 0
def update():
    for edge in edges:
        a,b,c = edge
        d[b] = min(d[b],d[a]+c)
for _ in range(N-1):
    update()
ansA = d[N]
for _ in range(N):
    update()
ansB = d[N]
if ansA == ansB:
    answer = -ansA
else:
    answer = 'inf'
print(answer)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [{} for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        adj[a][b] = c
    points = [-float("inf")] * (N+1)
    q = deque([(1, 0, {})])
    while len(q):
        cur, point, visited = q.popleft()
        if point <= points[cur]:
            continue
        points[cur] = max(points[cur], point)
        nvisited = {v: visited[v] for v in visited}
        nvisited[cur] = point
        for nxt in adj[cur]:
            npoint = point + adj[cur][nxt]
            if nxt in nvisited and nvisited[nxt] < npoint:
                npoint = float("inf")
            q.append((nxt, npoint, nvisited))
    print(points[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: -float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)
        self.x = 0
        self.y = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        c = 0
        while self.Q:
            c += 1
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
            if c == 2100:
                self.x = self.dist[N]
            if c >= 200000:
                self.y = self.dist[N]
                break
    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

g_a = Graph()
for i in range(M):
    a, b, w = list(map(int, input().split()))
    g_a.add_edge(a, b, w)

s = 1
d_a = Dijkstra(g_a, s)

if d_a.x == d_a.y:
    print(d_a.dist[N])
else:
    print("inf")

Submission status: Accepted

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

INF = 10 ** 20

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

dist = [INF for _ in range(n)]
dist[0] = 0

for i in range(n - 1):
    for a, b, c in abc:
        if dist[a] == INF:
            continue
        elif dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

ans = dist[n - 1]

check = [-1 for _ in range(n)]

for i in range(n - 1):
    for a, b, c in abc:
        if dist[a] == INF:
            continue
        elif dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            check[b] = 0

if check[n-1] == 0:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n-1):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
        if not update:
            break
    negative = [False for i in range(n)]
    for j, k, l in adj:
        if dist[k] > dist[j] + l:
            dist[k] = dist[j] + l
            negative[k] = True
    return dist,negative[n-1]
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,-c])
d,ne = bellman_ford(0)
if ne:
    print("inf")
else:
    print(-d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    e.append([a-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
v=0
while k<n*2:
    k+=1
    if k==n:v=d[-1]
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
if not v or v==d[-1]:
    print(-d[-1])
else:
    print('inf')

Submission status: Accepted

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

e = []

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

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print(maxdis[n-1])

Submission status: Accepted

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

e = []

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

maxdis = [-float('inf') for i in range(n)]

maxdis[0] = 0
mugen = False

for i in range(2*n):
    for j in e:
        st,gl,cost = j
        if (maxdis[gl] < maxdis[st]+cost):
            maxdis[gl] = maxdis[st]+cost
            if (i >= n-1 and (gl == n-1)): 
                mugen = True 
                break
if mugen:
    print("inf")

else:
    print(maxdis[n-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
INF = pow(10, 15)

alist, blist, clist = [], [], []
for _ in range(m):
  a, b, c = map(int, input().split())
  alist.append(a-1)
  blist.append(b-1)
  clist.append(-c)
dist = [INF for _ in range(n)]
dist[0] = 0
for _ in range(n-1):
  for a, b, c in zip(alist, blist, clist):
    if dist[a] == INF:  # まだ未到達なので更新しない
      continue
    if dist[b] > dist[a] + c:  # もし判明している到達コストよりも小さいなら
      dist[b] = dist[a] + c

ans = dist[n-1]

negative = [False for _ in range(n)]

for _ in range(n):
  for a, b, c in zip(alist, blist, clist):
    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:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
neg=[False]*(N+1)
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        neg[b]=True
    if neg[a]==True:
      neg[b]=True
if neg[N]:
  print("inf")
  exit(0)
print(allcost[N])

Submission status: Accepted

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


def shortest_path(s):
    #s→iの最短距離
    # s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    for j in range(n):
        updata = False
        for i in range(w):
            e = es[i]
            # e: 辺iについて [from,to,cost]
            if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                updata = True
        if not updata:
            break
    tmp = d[-1]
    for j in range(n):
        updata = False
        for i in range(w):
            e = es[i]
            # e: 辺iについて [from,to,cost]
            if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                updata = True
        if not updata:
            break
    if tmp == d[-1]:
        return d[-1]
    return float("inf")

n,w = map(int,input().split()) #n:頂点数　w:辺の数

es = []

for i in range(w):
    x,y,z = map(int,input().split())
    es.append([x-1,y-1,-z])
dj = shortest_path(0)
if dj == float("inf"):
    print('inf')
else:
    print(-dj)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
edges = defaultdict(list)
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edges[a].append((b, c))
INF = 10 ** 18

def bellman_ford():
    scores = [-INF] * N
    scores[0] = 0
    for i in range(N):
        for v in range(N):
            if scores[v] == -INF:
                continue
            for to, sc in edges[v]:
                if scores[v] + sc > scores[to]:
                    scores[to] = scores[v] + sc
                    if i == N - 1 and to == N - 1:
                        return 'inf'
    return scores[N - 1]

ans = bellman_ford()
print(ans)

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


inf=float("inf")
dist=[inf for i in range(n)]
dist[0]=0
flag = False
for i in range(2*n):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            if i >= n-1 and edge[1] == n-1:
                flag = True
                break
if flag:
    print("inf")
else:
    print(-dist[n-1])

Submission status: Accepted

Solution code:
# D
from math import isinf
N,M = map(int, input().split())
e = []
for _ in range(M):
    a,b,c = map(int, input().split())
    e.append((a-1,b-1,-c))

dists = [float('inf')] * N # 到達不能はinf
def bellman_ford(edges:list, start:int)->bool:
    """O(|V|*|E|)
    param v:
    param edges:
    return (exist negative loop)
    """
    global dists
    dists[start] = 0
    V = len(dists)
    for i in range(V):
        for (s,t,w) in edges:
            if isinf(dists[s]): continue
            if dists[t] > dists[s]+w:
                dists[t] = dists[s]+w
                if i==V-1 and t==V-1:
                    return True
        #print(dists)
    return False

negativeLoop = bellman_ford(e, 0)
if negativeLoop:
    print('inf')
else:
    print(-dists[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
es=[list(map(int,input().split())) for _ in range(m)]
inf=float("inf")
d=[-inf]*(n+1)
d[1]=0

def bellman_ford():
  for i in range(n):
    isUpdated=False
    for e_from,e_to,cost in es:
      if d[e_to]<d[e_from]+cost:
        d[e_to]=d[e_from]+cost
        isUpdated=True
        if i==n-1 and e_to==n:return inf
    if not isUpdated:
      break
  return d[n]

print(bellman_ford())

Submission status: Accepted

Solution code:
def BellmanFord(edges,num_vertex,start):
    inf=float("inf")
    dist=[inf for i in range(num_vertex)]
    dist[start]=0
    for i in range(num_vertex):
        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_vertex-1 and edge[1]==num_vertex-1:
                    return -1
    return dist

n,m=map(int,input().split())
edges=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    edges.append((a,b,-c))
dist=BellmanFord(edges,n,0)
if dist==-1:
    print("inf")
else:
    print(-dist[-1])

Submission status: Accepted

Solution code:
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N + 23):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N + 22 and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


def main():
    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])
    infFlag, ans = bellman_ford(N, M, edge)
    if infFlag:
        print('inf')
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N + 1):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


def main():
    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])
    infFlag, ans = bellman_ford(N, M, edge)
    if infFlag:
        print('inf')
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N - 1 and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


def main():
    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])
    infFlag, ans = bellman_ford(N, M, edge)
    if infFlag:
        print('inf')
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
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=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while count<n+1:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break
else:
    print(-d[n-1])

Submission status: Accepted

Solution code:
def BellmanFord(edges, num_v, source):
    #グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    #辺の和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                #負閉経路かつそれがゴールを通るもの、がある
                #i == num_v-1だけだと、負閉経路の検出だけになる
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = map(int, input().split())
edges = []
for _ in range(num_e):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print(-dist[-1])

Submission status: Accepted

Solution code:
def BellmanFord(edges, num_v, source):
    #グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    #変の和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

num_v, num_e = map(int, input().split())
edges = []
for _ in range(num_e):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print(-dist[-1])

Submission status: Accepted

Solution code:
# 入力「edges:隣接行列」「num_v:頂点数」「start:始点」
def shortest_path(edges, num_v, start):
    inf = float("inf")
    dist = [inf for _ in range(num_v)]
    dist[start] = 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 and edge[1] == num_v - 1:
                    print("inf")
                    exit()
    return dist

n, m = [int(i) for i in input().split()]
edges = []
for _ in range(m):
    a, b, c = [int(i) for i in input().split()]
    edges.append([a-1, b-1, -c])
out = shortest_path(edges,n,0)
print(-out[-1])

Submission status: Accepted

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

inf = float('inf')
d = [inf]*(N+1)
d[1] = 0
for i in range(N+1):
    for v, nv, cost in G:
        if d[v] != inf and d[nv] > d[v]+cost:
            d[nv] = d[v]+cost
            if i == N-1:
                tmp = d[N]
            if i == N and d[N] != tmp:
                print('inf')
                exit()
print(-d[N])

Submission status: Accepted

Solution code:
import sys


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


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

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N-1):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d

for a, b, c in edge:
    c = -c
    new_d = d[a]+c
    if d[b] > new_d:
        d[b] = new_d
        if b == N:
            print('inf')
            exit()
print(-d[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    # 0-indexed
    # コストの正負を逆転させれば最短経路問題として処理できる
    edges[i] = (a-1, b-1, -c)

def bellman_ford(N, edges, start):
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    verts = [float('inf')] * N
    verts[start] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    # 無限に減らせる場所がないか確認
    for src, dest, cost in edges:
        if verts[src] + cost < verts[dest]:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                # 頂点Nがそれに該当していたら空リストを返却
                return []
    # 問題なければ頂点リストを返却
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    # 正負を戻して出力
    print(-verts[N-1])

Submission status: Accepted

Solution code:
import sys


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


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

for _ in range(M):
    edge.append((list)(map(int, input().split())))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N):
    update = False
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            update = True

    if not update:
        break

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print(-d[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc061/editorial.pdf
・ベルマンフォード
・負の閉路があっても、そこに頂点Nが含まれなければ今回はOK
　って点に気付けなかったー。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    # 0-indexed
    # コストの正負を逆転させれば最短経路問題として処理できる
    edges[i] = (a-1, b-1, -c)

def bellman_ford(N: int, edges: list, start: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    verts = [float('inf')] * N
    verts[start] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
    # 無限に減らせる場所がないか確認
    for src, dest, cost in edges:
        if verts[dest] > verts[src] + cost:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                # 頂点Nがそれに該当していたら空リストを返却
                return []
    # 問題なければ頂点リストを返却
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    # 正負を戻して出力
    print(-verts[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc061/editorial.pdf
・ベルマンフォード
・負の閉路があっても、そこに頂点Nが含まれなければ今回はOK
　って点に気付けなかったー。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    # 0-indexed
    # コストの正負を逆転させれば最短経路問題として処理できる
    edges[i] = (a-1, b-1, -c)

def bellman_ford(N: int, edges: list, start: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    verts = [float('inf')] * N
    verts[start] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
    # 無限に減らせる場所がないか確認
    for i in range(N):
        for src, dest, cost in edges:
            if verts[dest] > verts[src] + cost:
                verts[dest] = verts[src] + cost
                if dest == N-1:
                    # 頂点Nがそれに該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    # 正負を戻して出力
    print(-verts[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    # 0-indexed
    # コストの正負を逆転させれば最短経路問題として処理できる
    edges[i] = (a-1, b-1, -c)

def bellman_ford(N: int, edges: list, start: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    verts = [float('inf')] * N
    verts[start] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    # 無限に減らせる場所がないか確認
    for src, dest, cost in edges:
        if verts[src] + cost < verts[dest]:
            verts[dest] = verts[src] + cost
            if dest == N-1:
                # 頂点Nがそれに該当していたら空リストを返却
                return []
    # 問題なければ頂点リストを返却
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    # 正負を戻して出力
    print(-verts[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・ベルマンフォード
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    # 0-indexed
    # コストの正負を逆転させれば最短経路問題として処理できる
    edges[i] = (a-1, b-1, -c)

def bellman_ford(N: int, edges: list, start: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    verts = [float('inf')] * N
    verts[start] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            verts[dest] = min(verts[src] + cost, verts[dest])
    # 無限に減らせる場所がないか確認
    for i in range(N):
        for src, dest, cost in edges:
            if verts[src] + cost < verts[dest]:
                verts[dest] = verts[src] + cost
                if dest == N-1:
                    # 頂点Nがそれに該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return verts

verts = bellman_ford(N, edges, 0)
if not verts:
    print('inf')
else:
    # 正負を戻して出力
    print(-verts[N-1])

Submission status: Accepted

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

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

for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()

print(-dist[-1])

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        """
        graph : [[a1,b1,c1],[a2,b2,c2],‥]みたいな3次元配列のリスト,a1からb1までのコストはc1
        num_v :頂点の数
        start_point :スタート地点(a1)
        """
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
 
 
    def execute(self):
        dist = [-1*float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        negative = [False for _ in range(self.num_v)]

        for i in range(self.num_v - 1):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost

        for i in range(self.num_v):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost
                    negative[end] = True
                if negative[start]:
                    negative[end] = True
        return dist, negative

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

bellman = BellmanFord(E, N, 0)
result, negative = bellman.execute()
 
if negative[-1]:
    print("inf")
else:
    print(result[-1])