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())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*k)

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print('inf')
else:
    print(-1 * ans)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in 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))

min_V = -1000000000 * 2000
scores = [min_V] * N
scores[0] = 0

for i in range(N):
    for a, b, c in E:
        if scores[b] >= scores[a] + c:
            continue
        scores[b] = scores[a] + c

ans = scores[N - 1]

for a, b, c in E:
    if scores[b] >= scores[a] + c:
        continue
    scores[b] = scores[a] + c

if ans != scores[N-1]:
    print("inf")
else:
    print(scores[N - 1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())
	A[i] -= 1
	B[i] -= 1
inf = 123456789123456789123456789
dist = [ -inf ] * N
dist[0] = 0
bounded = True
for i in range(max(2 * N - 3, 4)):
	for j in range(M):
		if dist[B[j]] < dist[A[j]] + C[j]:
			dist[B[j]] = dist[A[j]] + C[j]
			if B[j] == N - 1 and i >= N:
				bounded = False
if not bounded:
	print("inf")
else:
	print(dist[N - 1])

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [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 src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    negative[dest] = True
                if negative[src]:
                    negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a-1, b-1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

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

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [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 src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
                        negative[dest] = True
                    if negative[src]:
                        negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = -c
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

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

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
        self.negative = [False for _ in range(num_v)]

    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        for i in range(self.num_v - 1):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src, dest, cost in self.graph:
                if dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    self.negative[dest] = True
                if self.negative[src]:
                    self.negative[dest] = True
        return dist, self.negative


n, m = map(int, input().split())
graph = []

for i in range(m):
    a, b, c = map(int, input().split())
    graph.append([a - 1, b - 1, -c])
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

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

Submission status: Accepted

Solution code:
V, E = [int(_) for _ in input().split()]
G = {}

for i in range(V):
    G[i] = {}
for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = -c

INF = float('inf')

D = [INF] * V
D[0] = 0  # 0を始点とする場合
count = 0
while True:
    count += 1
    update = False
    update_n = False
    for s in G.keys():
        for t in G[s].keys():
            if D[s] != INF and D[t] > D[s] + G[s][t]:
                D[t] = D[s] + G[s][t]
                update = True
                if t == V - 1:
                    update_n = True
    if not update or count == V:
        break
if update_n:
    print('inf')
else:
    print(-D[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])
#edges = d
#num_v = n
#source = m


#ベルマンフォード
#高々|V|-1回で最安定経路にたどり着くっていうのがなかなか理解できなくて、紙に書きながら理解した。

"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    for i in range(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 2:
            k = d[-1]
        if i == num_v - 1 and k != d[-1]:
            d[n - 1] = -inf
            break
    return d

print(-shortest_path(edge,n,0)[n - 1])
#print("inf")
#print(BellmanFord(e, n, m))
"""5 5
1 2 2
2 5 4
4 3 1
3 4 2
2 4 1"""

Submission status: Accepted

Solution code:
def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
        if i==n-1:t=d[-1]
        if i==n and t!=d[-1]:
            return [0,'inf']
    return list(map(lambda x:-x, d))
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a=[[x,y,-z] for x,y,z in a]
print(BF(a, n, 1)[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
inf = 10**15
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                if d[b]<d[a]+c:
                    d[b] = d[a]+c
                    update = True
            else:
                update = True
                d[b] = d[a] + c
    if not update:
        break

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                if not updated[b]:
                    update = True
                    updated[b] = True
        if updated[a] and not updated[b]:
            update = True
            updated[b] = True
    if not update:
        break

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

Submission status: Accepted

Solution code:
def BF(N, edges, start):
    D = {}
    P = {}
    for i in range(N):
        P[i] = None
        if i == start:
            D[i] = 0
        else:
            D[i] = float("inf")

    for i in range(N-1):
        for edge in edges:
            a, b, c = edge
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a

    ret = (D, P)

    Nega = {}
    for i in range(N):
        Nega[i] = False
    
    for i in range(N):
        for edge in edges:
            a, b, c = edge
            if Nega[a] == True:
                Nega[b] = True
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a
                Nega[b] = True
        
    return (D, P, Nega)


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

D, P, Nega = BF(N, edges, 0)

if Nega[N-1]:
    print("inf")
else:
    print(-D[N-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges=[]
for m 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
dist_n=[inf for i in range(N)]
negative=[-1 for i in range(N)]
for i in range(N-1):
  for e in edges:
    if dist[e[1]]>dist[e[0]]+e[2]:
      dist[e[1]]=dist[e[0]]+e[2]  
for i in range(N):
  for e in edges:
    if negative[e[0]]>0:
      negative[e[1]]=1
    if dist[e[1]]>dist[e[0]]+e[2]:
      dist[e[1]]=dist[e[0]]+e[2]
      negative[e[1]]=1
if negative[N-1]>0: 
  print(inf)
else:
  print(-dist[N-1])

Submission status: Accepted

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

edge=[[] for _ in range(N)]
dist=[-float('inf') for _ in range(N)]
dist[0]=0

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

tmp=-float('inf')
for n in range(N):
    flag=0
    tmp=dist[-1]
    for i in range(N):
        for b,p in edge[i]:
            if dist[b]<dist[i]+p:
                dist[b]=dist[i]+p
                flag=1
    if flag==0:
        break
if tmp!=dist[-1]:
    print('inf')
else:
    print(int(dist[-1]))

Submission status: Accepted

Solution code:
V, E=map(int,input().strip().split(' '))
edge=[]
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    edge.append([at,bt,ct])

#edge=[[0,1,2],[0,2,5],[1,2,4],[1,3,6],[2,3,2],[1,4,10],[3,5,1],[4,5,3],[4,6,5],[5,6,9],[1,0,2],[2,0,5],[2,1,4],[3,1,6],[3,2,2],[4,1,10],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]
#V=7
#E=10*2
inf=-3*10**15

def shortest_path(s):
    d=[inf]*V
    d[s]=0
    for _ in range(V+1):
        update=False
        for i in range(E):
            if d[edge[i][0]-1]!=inf and d[edge[i][1]-1]<d[edge[i][0]-1]+edge[i][2]:
                d[edge[i][1]-1]=d[edge[i][0]-1]+edge[i][2]
                update=True
        if update==False:
            break
        if _ == V-1:
            tm=d[V-1]
        if _ == V and d[V-1]!=tm:
            return False
    return d

d=shortest_path(0)
if d==False:
    print('inf')
else:
    print(d[V-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())
    a, b = a - 1, b - 1
    c = -c
    E.append([a, b, c])

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

for n in range(N):
    for a, b, c in E:
        if (dist[a] != float('inf')) & (dist[b] > dist[a] + c):
            dist[b] = dist[a] + c
            if (n == N - 1) & (b == N - 1):
                print('inf')
                exit()

print(-dist[N - 1])

Submission status: Accepted

Solution code:
#061-D
#v,Eは、頂点(vertex),辺(edge)の数
v,E=map(int,input().split())
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,c])
d=[None for i in range(v)]
for i in range(v):
    d[i]=-float('INF')
d[0]=0
for i in range(v-1):
    update=False
    for i in range(E):
        if d[e[i][0]]!=-float('INF') and d[e[i][1]]<d[e[i][0]]+e[i][2]:
            d[e[i][1]]=d[e[i][0]]+e[i][2]
            update=True
    if not update:
        break
ans=d[v-1]
for i in range(E):
    if d[e[i][0]]!=-float('INF') and d[e[i][1]]<d[e[i][0]]+e[i][2]:
        d[e[i][1]]=d[e[i][0]]+e[i][2]
print(ans if ans==d[v-1] else 'inf')

Submission status: Accepted

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v


# Even if a negative weight exists, bellman-ford can find shortest paths.
# it also detects negative cycles,
# but not all edges that consist the negative cycles is stored.
# time complexity: O(VE + (V^2))
def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    # calculate shortest paths
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    # detects negative cycles if exist
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if len(negative_cycle_edges) > 0:
    # see if there's a path from 0 to this edge via DFS
    stack = [0]
    visited = set()
    visited.add(0)
    reachable_edges = set()
    while stack:
        source = stack.pop()
        for neighbor in adj[source]:
            if (source, neighbor) in negative_cycle_edges:
                reachable_edges.add((source, neighbor))
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    # see if there is a path to N - 1
    for _, target in reachable_edges:
        stack = [target]
        visited = set()
        visited.add(target)
        while stack:
            source = stack.pop()
            for neighbor in adj[source]:
                if neighbor == N - 1:
                    print("inf")
                    exit(0)
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    else:
        print(-d[N - 1])
else:
    print(-d[N - 1])

Submission status: Accepted

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v


# Even if a negative weight exists, bellman-ford can find shortest paths.
# it also detects negative cycles,
# but not every edges that consist the negative cycles is stored.
# time complexity: O(VE + (V^2))
def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    # calculate shortest paths
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    # detects negative cycles if exist
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if len(negative_cycle_edges) > 0:
    # see if there's a path from 0 to this edge via DFS
    stack = [0]
    visited = set()
    visited.add(0)
    reachable_edges = set()
    while stack:
        source = stack.pop()
        for neighbor in adj[source]:
            if (source, neighbor) in negative_cycle_edges:
                reachable_edges.add((source, neighbor))
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    # see if there is a path to N - 1
    for _, target in reachable_edges:
        stack = [target]
        visited = set()
        visited.add(target)
        while stack:
            source = stack.pop()
            for neighbor in adj[source]:
                if neighbor == N - 1:
                    print("inf")
                    exit(0)
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    else:
        print(-d[N - 1])
else:
    print(-d[N - 1])

Submission status: Accepted

Solution code:
import queue

class Graph:

    INF = 10**27+1
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list


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

G = Graph(N,True)

for i in range(M):
    a,b,c = list(map(int,input().split()))
    G.appendEdge(a-1,b-1,-c)
    
res=G.getSSSPwithBellmanFord(0)

if res[2][N-1]:
    print('inf')
else:
    print(-res[0][N-1])

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, M = inpl()
inf = float('inf')
path = [0 for _ in range(M)]
score = [-inf]*N
score[0] = 0
ans = 0
for i in range(M):
    a, b, c = inpl()
    path[i] = (a-1,b-1,c)

for i in range(N-1):
    update = False
    for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
            update = True
    if not update:
        break
ans = score[N-1]
for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
print(ans if ans == score[N-1] else 'inf')

Submission status: Accepted

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

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

ans = d[N-1]
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost

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

Submission status: Accepted

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

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[N-1]
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost

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

Submission status: Accepted

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

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
ans = d[N-1]
for i in range(V):
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(m)]
abc=[[t[0],t[1],-t[2]] for t in abc]
def BF(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
  
    #辺の緩和
    neg=[False for _ in range(num_v)]
    for i in range(num_v-1):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                neg[edge[1]-1]=True
            if neg[edge[0]-1]==True:
                neg[edge[1]-1]=True
    return dist,neg
dis,neg=BF(abc,n,1)
#print(dis,neg)
if neg[-1]:
    print("inf")
else:
    print(-dis[-1])

Submission status: Accepted

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                d[b] = d[a] + c

ne = [False] * N
ans = -d[N - 1]
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                ne[b] = True
                d[b] = d[a] + c

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

if ne[N - 1]:
    print("inf")
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 18
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] - c)

ans = dist[N]
for a, b, c in edges:
    dist[b] = min(dist[b], dist[a] - c)

if ans != dist[N]:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

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

Cost = [float("inf") for i in range(N)]
V = [False for i in range(N)]
Cost[0] = 0
for i in range(N-1):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            if Cost[j[1]] != float("inf"):
                V[j[1]] = True
            Cost[j[1]] = Cost[j[0]] + j[2]     
        if V[j[0]] == True:
            V[j[1]] = True
ans = -Cost[N-1]

for j in P:
    if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
        if Cost[j[1]] != float("inf"):
            V[j[1]] = True
        Cost[j[1]] = Cost[j[0]] + j[2]    
    if V[j[0]] == True:
        V[j[1]] = True

print("inf" if V[N-1] else ans)

Submission status: Accepted

Solution code:
# ABC 061 D
# Bellman-Ford

N, M = map(int, input().split())
INF = float("inf")

G = []
# from a to b cost c
for k in range(M):
    a, b, c = map(int, input().split())
    G.append([a-1,b-1,-c])

dist = [INF for k in range(N)]
dist[0] = 0

for k in range(N-1):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

# find a negative loop
negative = [0 for k in range(N)]
for k in range(N):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            negative[b] = 1
        if negative[a] == 1:
            negative[b] = 1

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

Submission status: Accepted

Solution code:
inf = int(1e20)
node,edge = map(int,input().split())
ed = []
for i in range(edge):
    e = list(map(int,input().split()))
    ed.append((e[0]-1,e[1]-1,-e[2]))
start = 0
goal = node-1



d = [inf for i in range(node)]
pre = [inf for i in range(node)]
d[start] = 0

for i in range(node):
    update = False
    for e in ed:
        if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
            d[e[1]] = d[e[0]]+e[2]
            update = True
            pre[e[1]] = e[0]
    if update==False:
        print(-d[goal])
        break
else:
    nowcos = d[goal]
    for i in range(node):
        for e in ed:
            if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
                d[e[1]] = d[e[0]]+e[2]
                pre[e[1]] = e[0]
    if nowcos != d[goal]:
        print('inf')
    else:
        print(-d[goal])

Submission status: Accepted

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

dist = [INF for i in range(N)]
dist[0] = 0

neg_cycle = False
for i in range(N+1):
	update = False
	N_update = False
	for (a,b,c) in edge:
		if dist[a] == INF:
			continue

		if dist[a] + c < dist[b]:
			dist[b] = dist[a] + c
			update = True
			if b == N-1:
				N_update = True

	if not update:
		break
	if i >= N - 1 and N_update:
		neg_cycle = True

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