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:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    tmp = MIN
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if cnt == m: tmp = d[n]
        if update and cnt == 2 * m and d[n] > tmp: return 'inf'
        if cnt == 2 * m: update = False
        cnt += 1
    return d[n]

print(shortest_path(1))

Submission status: Accepted

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

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

INF = float('inf')

def find_negative_loop(n,es,s):
    #負の経路の検出
    #n:頂点数, es[i]: [辺の始点,辺の終点,辺のコスト], s:始点
    dist = [-INF] * n
    dist[s] = 0

    for i in range(n):
        for a,b,c in es:
            if dist[b] < dist[a]+c:
                dist[b] = dist[a]+c
                # if i == n-1: # n回目にも更新が行われている場合，ループが存在する
                if i == n-1 and b==n-1: # 終点に影響を及ぼすループが存在する
                        return INF
    return dist[n-1]

ans = find_negative_loop(n,es,0)

if ans == INF:
    print('inf')
    exit()

print(ans)

Submission status: Accepted

Solution code:
def BellmanFord(s,N,Edge):
    INF=float("inf")
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg

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

Submission status: Accepted

Solution code:
class Edge:

    def __init__(self, from_node, to_node, weight):
        self.from_node = from_node
        self.to_node = to_node
        self.weight = weight


def bellman_ford(N, edges, start, goal):
    # Weight Maximization
    MIN_INF = - 10**15
    d = [MIN_INF for _ in range(N)]
    d[start] = 0
    for loop in range(N):
        updated = False
        goal_updated = False
        for edge in edges:
            new_d = edge.weight + d[edge.from_node]
            if d[edge.to_node] < new_d:
                d[edge.to_node] = new_d
                updated = True
                if edge.to_node == goal:
                    goal_updated = True
        if not updated:
            return d[goal]
        if loop == N - 1:
            if not goal_updated:
                return d[goal]
            # exists a positive loop which connected to the goal node.
            return None


def main():
    N, M = list(map(int, input().split(' ')))
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        from_node = a - 1 
        to_node = b - 1
        weight = c
        edges.append(Edge(from_node, to_node, weight))
    start, goal = 0, N - 1
    result = bellman_ford(N, edges, start, goal)
    if result is None:
        print('inf')
    else:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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


def bellman_ford(edges, N, start):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0
    # 辺の情報を見ることを1ループとすると
    # 1回のループで,最低でも1つの頂点について，スタートからの最短距離が求まる
    # つまり,スタートからの全ての頂点への距離は，
    # スタートを除いた頂点の数である,(N-1)回のループで求まる．
    for i in range(2 * N):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] - cost:
                dist[to] = dist[fro] - cost
                # N回目に頂点の更新があると，負の経路がある
                if i == N - 1:
                    dist[to] = -float("inf")
    return dist


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))
    D = bellman_ford(edge, N, 0)

    print(-1 * D[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    pass


if __name__ == "__main__":
    main()


def bellman_ford(edges, N, start, goal):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0

    # 辺の情報を見ることを1ループとすると
    # 最低でも1つの頂点について，スタートからの最短距離が求まる
    # つまり，スタートからの距離は，スタートを除いた頂点の数である
    # (N-1)回のループで求まる．
    for i in range(N * 2):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                # N回目に頂点の更新があると，負の経路がある
                if i == N - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


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

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

cost = [float("inf") for _ in range(N)]
start = 0
goal = N - 1
ans = bellman_ford(edges, N, start, goal)
if ans == float("inf"):
    print(ans)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
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))
dist,neg=Belman_Ford(0,N,Edge)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')

Submission status: Accepted

Solution code:
V,M = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(M)]
G = [list() for i in range(V)]
for a,b,c in abc:
    G[b-1].append((a-1,-c))
INF = 10**18
dist = [INF] * V
dist[V-1] = 0
update = 1
for _ in range(V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
    print('inf')
    exit()
print(-dist[0])

Submission status: Accepted

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[f]!=INF and dist[t]>dist[f]+c:
                dist[t]=min(dist[t],dist[f]+c)
    F=[False]*N
    for j in range(N):
        for f,t,c in Edge:
            if(dist[t]>dist[f]+c):
                dist[t]=dist[f]+c
                F[t]=True
    if F[N-1]:
        return 'inf'
    else:
        return -dist[N-1]
    
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Accepted

Solution code:
INF=10**50

def Bellman_Ford(s,N,Edge):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    while True:
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if dist[f]!=INF:
                    dist[t]=min(dist[t],dist[f]+c)
                    update=True
                    if cnt==N-1 and t==N-1:
                        print('inf')
                        exit()
        if not update or cnt==N-1:
            break
        cnt+=1
    return -dist[N-1]
N,M=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b,c=a-1,b-1,-c
    Edge.append([a,b,c])
print(Bellman_Ford(0,N,Edge))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
abc = [tuple(na()) for i in range(m)]

dp = [float('inf')]*n
dp[0] = 0

for i in range(n):
    for a,b,c in abc:
        a,b,c = a-1,b-1,-c
        if dp[a] != float('inf') and dp[b] > dp[a] + c:
            dp[b] = dp[a] + c
            if i == n-1 and b == n-1:
                print('inf')
                exit()

print(-dp[-1])

Submission status: Accepted

Solution code:
def resolve():
    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])


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))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self,gorl):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[gorl]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans if self.ans == self.dist[gorl] else '-inf'

n,m = map(int,input().split())

bf = BellmanFord(n,0)

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

ans = bf.build(n-1)
if ans == '-inf':
    print('inf')
else:
    print(- ans)

Submission status: Accepted

Solution code:
class BellmanFord:
    def __init__(self,v,start):
        self.inf = float('inf')
        self.dist = [self.inf]*v
        self.dist[start] = 0
        self.edge = []
        self.v = v
    
    def add(self,f,t,cost):
        self.edge.append((f,t,cost))
    
    def build(self):
        for _ in range(self.v - 1):
            for f,t,cost in self.edge:
                if self.dist[t] > self.dist[f] + cost:
                    self.dist[t] = self.dist[f] + cost
        self.ans = self.dist[n-1]
        for f,t,cost in self.edge:
            if self.dist[t] > self.dist[f] + cost:
                self.dist[t] = self.dist[f] + cost
        return self.ans == self.dist[n-1]

n,m = map(int,input().split())

bf = BellmanFord(n,0)

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

if bf.build():
    print(- bf.ans)
else:
    print('inf')

Submission status: Accepted

Solution code:
import sys

N, M = map(int,input().split())
es = []
for _ in range(M):
    e = list(map(int,input().split()))
    e[2] *= -1
    es.append(e)

INF = float('inf')
d = [INF for _ in range(N+1)]
d[1] = 0
negative = [0 for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        e = es[j]
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            if i == N-1:
                negative[e[0]] = 1
                negative[e[1]] = 1
for i in range(M):
    e = es[i]
    if negative[e[0]]:
        negative[e[1]] = 1
if negative[N]:
    print('inf')
else:
    print(-d[N])

Submission status: Accepted

Solution code:
# solution
import io

nim,mike=map(int,input().split())

abc=[list(map(int,input().split())) for _ in [0]*mike]

g=[[] for _ in [0]*nim]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*nim]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(nim):
    for p in range(nim):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[nim-1]

if a==b:
    print(a)
else:
    print("inf")

Submission status: Accepted

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

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1 and w == n - 1:
                        return -1
    return dist

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
    dist = bellmanford(graph, 0)
    if dist == -1:
        print("inf")
    else:
        print(dist[N-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bellmanford(G, s):
    n = len(G)
    inf = -float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(2*n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] < dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1 and w == n-1:
                        return -1
    return dist

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
    dist = bellmanford(graph, 0)
    if dist == -1:
        print("inf")
    else:
        print(dist[N-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = -1 * abc[i][2]
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c
# print(abc)

# 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 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 False,[]
#     return True,dist

# sからiへの最短距離を求める（Bellman-Ford法）
# s:始点，n:頂点数，w:辺の数，es[i]:[辺の始点,辺の終点,辺のコスト]
def BellmanFord(s,n,w,es):
    # 初期化
    d = [float("inf")]*n
    d[s] = 0
    # 更新
    for i in range(n):
        # update = False
        for p,q,r in es:
            # [p,q,r] = [from, to, cost]
            if d[p]!=float("inf") and d[q]>(d[p]+r):
                d[q] = d[p] + r
                # update = True
                if i==(n-1) and q==(n-1):
                    return False,[]
        # if update:
        #     pass
        # else:
        #     break
    return True,d

# def find_negative_loop(s,n,w,es):
#     #負の経路の検出
#     #n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
#     d = [float("inf")] * n
#     d[s] = 0
#     #この始点はどこでもよい <----よくない
#     for i in range(n):
#         for j in range(w):
#             e = es[j]
#             if d[e[1]] > d[e[0]] + e[2]:
#                 d[e[1]] = d[e[0]] + e[2]
#                 if i==(n-1):
#                     return True
#     return False

flag,distance = BellmanFord(0,n,m,abc)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

Submission status: Accepted

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

N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))
dist = [float('inf')] * (N+1)
dist[1] = 0
for _ in range(N-1):
    for u, v, weight in edges:
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
negative = [False] * (N+1)
for _ in range(N):
    for u, v, weight in edges:
        if dist[v] > dist[u] + weight:
            dist[v] = dist[u] + weight
            negative[v] = True
print('inf' if negative[N] else -dist[N])

Submission status: Accepted

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

stack = [0]
can_reach = [0]*n
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)

INF = 10**18
dist = [INF]*n
dist[0] = 0
for i in range(n-1):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1


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

Submission status: Accepted

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

stack = [0]
can_reach = [0]*n
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)

INF = 10**18
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n*2):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1

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

Submission status: Accepted

Solution code:
from collections import deque


def main():

    N, M = map(int, input().split())
    E = [list(map(int, input().split())) for _ in range(M)]

    # make graph
    G = [set() for _ in range(N)]
    for i in range(M):
        E[i][0], E[i][1] = E[i][0] - 1, E[i][1] - 1
        G[E[i][0]].add(E[i][1])

    def bfs(s):
        # find connected vertex by bfs
        vis_loc = [False] * N
        vis_loc[s] = True
        q = deque([s])
        while len(q):
            v = q.popleft()
            for n in G[v]:
                if vis_loc[n]:
                    continue
                q.append(n)
                vis_loc[n] = True
        return vis_loc
    vis = bfs(0)
    C = []
    for i in range(M):
        if vis[E[i][0]]:
            C.append(i)

    # Bellman-Ford
    N_con = sum(vis)
    ans = [float('inf')] * N
    ans[0] = 0
    for i in range(N_con):
        ud = -1
        for j in C:
            a, b, c = E[j]
            if ans[b] > ans[a] - c:
                ans[b] = ans[a] - c
                ud = a
        if ud == -1:
            break
        else:
            if i == N_con - 1:
                if bfs(ud)[N - 1]:
                    print('inf')
                    exit()
    print(-ans[N - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


N, M = map(int, input().split())
edge = []
for s in sys.stdin.readlines():
    a, b, c = map(int, s.split())
    edge.append((a - 1, b - 1, c))

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

for i in range(N - 1):
    for j in range(M):
        a, b, c = edge[j]
        if path[b] < path[a] + c:
            path[b] = path[a] + c


for i in range(N - 1):
    for j in range(M):
        a, b, c = edge[j]
        if path[b] < path[a] + c:
            path[b] = float('inf')

print(path[-1])

Submission status: Accepted

Solution code:
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))

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
negative_cycle = 0
for i in range(2*n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        if i >= n-1 and v2 == n-1:
            negative_cycle = 1

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

Submission status: Accepted

Solution code:
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))

init_v = 0
INF = float('inf')
dist = [INF]*n
dist[init_v] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        negative[v2] = 1

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

Submission status: Accepted

Solution code:
def bellman_ford(edges, N, start, end):
    cost = [float("inf") for _ in range(N)]
    cost[start] = 0
    negative = [False for _ in range(N)]

    for i in range(N):
        for j in range(len(edges)):
            fro, to, c = edges[j]

            if cost[to] > cost[fro] + c:
                cost[to] = cost[fro] + c
                # 頂点の数と同じ回数ループすると負の経路がある
                if i == N - 1:
                    negative[to] = True

    if negative[end]:
        return "inf"
    else:
        return -cost[end]


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

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

cost = [float("inf") for _ in range(N)]
start = 0
end = N - 1
print(bellman_ford(edges, N, start, end))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]


#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n-1):
        for j in range(w):
            e = es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
    neg=[False]*n
    for i in range(n):
        for j in range(w):
            e=es[j]
            if d[e[1]-1] > d[e[0]-1] - e[2]:
                d[e[1]-1] = d[e[0]-1] - e[2]
                neg[e[1]-1]=True
            if neg[e[0]-1]==True:
                neg[e[1]-1]=True
    return (d,neg)


#############################
ans=find_negative_loop(n,m,abc)
if ans[1][-1]==True:
    print("inf")
else:
    print(-ans[0][-1])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
class BellmanFord():
    """ベルマンフォード法で最短経路を求める"""
    def __init__(self, s, V):
        """
        Args:
            s(int): 始点
            V(int): 頂点数
        """
        self.graph = {}
        for i in range(V):
            self.graph[i] = []
        self._V = V
        self.dst = [float("inf") for _ in range(V)]
        self.dst[s] = 0

    @property
    def dist(self):
        return self.dst

    @property
    def V(self):
        return self._V

    def add(self, a, b, cost):
        """頂点aから頂点bへのコストはcost"""
        self.graph[a].append((b, cost))

    def shortest_path(self):
        """始点sからの最短経路を求める
        Returns:
            (bool): 負の閉路が存在する(True) / 存在しない(False)
        """
        for t in range(self.V):
            update = False
            for u in range(self.V):
                if self.dst[u] == float("inf"): continue
                for v, cost in self.graph[u]:
                    if self.dst[v] > self.dst[u] + cost:
                        self.dst[v] = self.dst[u] + cost
                        update = True

                        if t == self.V-1 and v == self.V-1:
                            return True

            if not update:
                break

        return False


def solve():
    N, M = map(int, input().split())
    bf = BellmanFord(0, N)

    for _ in range(M):
        a, b, c = map(int, input().split())
        bf.add(a-1, b-1, -c)

    nloop = bf.shortest_path()

    if nloop:
        print("inf")
    else:
        print(-bf.dist[N-1])


if __name__ == "__main__":
    solve()