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 = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]

INF = - 10 ** 20
d = [INF for _ in range(N)]
d[0] = 0

for i in range(2 * N):
  f = True
  rel = d[-1]
  for j in range(M):
    a, b, c = abc[j]
    a -= 1
    b -= 1
    if d[b] < d[a] + c:
      d[b] = d[a] + c
      f = False
  if f:
    break
else:
  if rel != d[-1]:
    print("inf")
    exit()

print(d[-1])

Submission status: Accepted

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

INF = 10 ** 13
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')

Submission status: Accepted

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

INF = 10 ** 13

G = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = -c
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')

Submission status: Accepted

Solution code:
def BellmanFord(edges,num_v,source):
  dist=[float("inf") for i in range(num_v)]
  dist[source]=0
  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != float("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] == N - 1:
            return -1
  
  return dist

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

d  = BellmanFord(edges,N,0)
if d==-1:
    print("inf")
    exit()

print(-d[N-1])

Submission status: Accepted

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

for i in range(M):
    edges[i][2] *= -1

INF = 10 ** 20
d = [INF] * (N + 1)

def bellman_ford():    
    d[1] = 0
    for _ in range(N):
        for u, v, c in edges:
            if (d[u] != INF) and (d[v] > d[u] + c):
                d[v] = d[u] + c

negative = [False] * (N + 1)

def bellman_ford_neg():
    for _ in range(N):
        for u, v, c in edges:
            if (d[u] != INF) and (d[v] > d[u] + c):
                d[v] = d[u] + c
                negative[v] = True
                
            if negative[u]:
                negative[v] = True

bellman_ford()
bellman_ford_neg()

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

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
import sys
edges = []
dist = [sys.maxint]*(n+1)
dist[1] = 0
dist
for _ in range(m):
    a, b, c = map(int, raw_input().split())
    edges.append((a, b, -c))

for i in range(n-1):
    for a, b, c in edges:
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
negative = [False] *(n+1)
for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b] or negative[a]:
            negative[b] = True
if negative[n]:
    print "inf"
else:
    print -dist[n]

Submission status: Accepted

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

inf = float('inf')

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[V-1]
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
if ans != -d[V-1]:
    print('inf')
else:
    print(ans)

Submission status: Accepted

Solution code:
#https://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
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())
g=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  g.append([a,b,-c])
print(BF(g,n,1)[-1])

Submission status: Accepted

Solution code:
N,E=map(int,input().split())
G=[]
for i in range(E):
    a,b,c=map(int,input().split())
    G.append([-c,a-1,b-1])
def bellman_ford(G,s):
    INF=10**18
    d=[INF]*N
    d[s]=0
    j=0
    while(True):
        update=False
        for i in range(E):
            cost,fro,to=G[i]
            if d[fro]!=INF and d[to]>d[fro]+cost:
                d[to]=d[fro]+cost
                update=True
                if j==N-1 and to==N-1:
                    return True,0#負の閉路あり
        if j==N-1:
            return False,d
        j+=1
        if not(update):
            break
    return False,d#負の閉路なし、ｓからの最短距離ｄ
bool,d=bellman_ford(G,0)
if bool:
    print("inf")
else:
    print(-d[N-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = [False]*N
        for v in V:
            d = dist[v]
            if d != INF:
                for u, c in E[v].items():
                    temp = d + c
                    if dist[u] > temp:
                        updated[u] = True
                        dist[u] = temp
        if sum(updated) == 0: # the minimum costs are already stored in dist
            break
    else: # the above loop is not broken if and only if there exists a negative cycle
        if updated[N-1]: return None
        else: return dist
    return dist

N, M = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = -c
V = list(range(N))
dist = bellman_ford(V, E, 0)
if dist is None:
    print('inf')
else:
    print(-dist[N-1])

Submission status: Accepted

Solution code:
#ベルマンフォード法
#https://atcoder.jp/contests/abc061/submissions/6001032
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0
d_tmp = 0

for abci in abc: #
    if dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

d_tmp = dist[-1]
for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]    


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

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float("inf")
dist = [INF]*N
dist[0] = 0
d_tmp = 0

for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]

d_tmp = dist[-1]
for abci in abc:
    if dist[abci[0]-1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
         dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]    


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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
sys.setrecursionlimit(200000)

graph = [[] for _ in range(N + 1)]

for a, b, c in ABC:
    graph[b].append((a, c))
graph[1].append((0, 0))

vd = [(N, 0)]
# N までの最長距離
ans = [-INF] * (N + 1)
ans[N] = 0
for _ in range(N + 1):
    nexts = []
    for v, d in vd:
        for u, c in graph[v]:
            if ans[u] < d + c:
                ans[u] = d + c
                nexts.append((u, d + c))
    vd = nexts
if vd:
    print('inf')
else:
    print(ans[0])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict,deque
branch=defaultdict(dict)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
inf=10**15
dist=[(-inf,set())]*N
dist[0]=(0,{0})
check={0}
while len(check)>0:
    now=check.pop()
    for nex,s in branch[now].items():
        if dist[nex][0]>=inf:
            continue
        if nex not in dist[now][1]:
            dist[nex]=(dist[now][0]+s,dist[now][1]|{nex})
            check|={nex}
        elif dist[now][0]+s>dist[nex][0]:
            dist[nex]=(inf,dist[now][1]|{nex})
            check|={nex}
if dist[N-1][0]>=inf:
    print('inf')
else:
    print(dist[N-1][0])

Submission status: Accepted

Solution code:
INF = float('inf')
#vは頂点数、eは辺数
#s番目の頂点から各頂点への最短距離を求める
def Bellmanford(n, e, s):
  d = [INF]*n
  d[s] = 0
  for i in range(n):
    for e_from, e_to, e_cost in e:
      if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
        d[e_to] = d[e_from] + e_cost
        if i == n-1 and e_to == n-1:
          return 'inf'
  return -d[n-1]

n,m = (int(x) for x in input().split())
edges = [None] * m

for i in range(m):
    ai, bi, ci = map(int, input().split())
    edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(n, edges, 0)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:
import sys
sys.setrecursionlimit(100000)

N, M = [int(ele) for ele in input().split()]
edges = []

d = [-100000000000000000000000000000000000000000000000] * (N+1)
d_tmp = []

for _ in range(M):
    src, dst, w = [int(ele) for ele in input().split()]
    if src == 1:
        d[dst] = w
    edges.append([src, dst, w])

yet = [ele for ele in range(1, N+1)]


def main():
    print(d[-1] if bellman_ford() != -1 else "inf")


def bellman_ford():
    for _ in range(N - 1):
        for src, dst, w in edges:
            if d[dst] < w + d[src]:
                d[dst] = w + d[src]

    d_tmp = d[-1]

    for src, dst, w in edges:
        if d[dst] < w + d[src]:
            d[dst] = w + d[src]

    if d_tmp != d[-1]:
        return -1

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########
class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1 and edge.to_edge == (node_num - 1):
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)
# print(dist)
if flag:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########
class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False
    for i in range(node_num):
        for edge in edges:
            if edge.from_edge != INF and dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1 and edge.to_edge == (node_num - 1):
                    flag = True
    return dist, flag


N, M = l_inpl()
edges = []

for _ in range(M):
    ai, bi, ci = l_inpl()
    edges.append(Edge(ai-1, bi-1, -ci))

dist, flag = bellman_ford(0, edges, N)
# print(dist)
if flag:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Accepted

Solution code:
from operator import itemgetter

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+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]
        if i==num_v and edge[1]==num_v: return -1

  return dist


#%%
N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)
#%%
route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-int(route[N-1]))

Submission status: Accepted

Solution code:
INF = float('inf')


def Bellmanford(node, edges, source):
    d = [INF] * node  # ある頂点までのコストを保存するリスト
    d[source] = 0

    for i in range(node):
        for start, goal, cost in edges:
            # 辺の始まりの頂点までのコストが INF でなく
            # 辺の向かう先の頂点のコストが、より軽くなる場合に、
            # リストを更新する
            if d[start] != INF and d[start] + cost < d[goal]:
                d[goal] = d[start] + cost
                if i == node-1 and goal == node-1:
                    return 'inf'
    return -d[node-1]


N, M = map(int, input().split())
abc = [map(int, input().split()) for _ in range(M)]
Edges = [None] * M

for i in range(M):
    ai, bi, ci = abc[i]
    Edges[i] = (ai-1, bi-1, -ci)


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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))

    #edgeは1次元ですべて(始点,終点,重み)を格納
    def bellmanford(edge):
        costs = [inf] * N
        costs[0] = 0
        exist_minus_cycle = False
        for i in range(N):
            update = False
            for from_, to, cost in edge:
                cost_to = costs[from_] + cost
                if cost_to < costs[to]:
                    update = True
                    costs[to] = cost_to
                    
            if not update:
                break
            elif i==N-1:
                exist_minus_cycle = True

        #どこで無限に更新されるか判定
        minus_cycle = set()
        if exist_minus_cycle:
            for i in range(N+1):
                for from_, to, cost in edge:
                    cost_to = costs[from_] + cost
                    if from_ in minus_cycle:
                        minus_cycle.add(to)
                    if cost_to < costs[to]:
                        minus_cycle.add(from_)
                        minus_cycle.add(to)
                        costs[to] = cost_to
        return costs, minus_cycle
    
    costs,minus_cycle = bellmanford(edge)


    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-costs[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                
        if not update:
            break
        elif i==N-1:
            exist_minus_cycle = True

    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(from_)
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [[] for i in range(w)] #es[i]: [辺の始点,辺の終点,辺のコスト]
for i in range(w):
    x,y,z = map(int,input().split())
    es[i] = [x,y,-z]
    #es[2*i+1] = [y,x,z]
w = w

d = [10**20] * (n+1)
d[1] = 0

def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    

    #この始点はどこでもよい
    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]
                
    return d
find_negative_loop(n,w,es)

#print(es)
#print(d)
D=copy.deepcopy(d)
find_negative_loop(n,w,es)
                
#print(d)
if d[n]==D[n]:
    print(-D[n])
else:
    print("inf")
#print(d)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

def bellman_ford(V,G,start=0):
    dist = [inf]*V
    dist[start]=0
    negative_cycle = False
    for _ in range(1,V):
        for u in G:
            for v,d in G[u]:
                if dist[v]>dist[u]+d:
                    dist[v] = dist[u]+d
    ans = dist[V-1]
    for u in G:
        for v,d in G[u]:
            if dist[v] > dist[u]+d:
                dist[v] = dist[u]+d
    if dist[V-1]<ans:
        return -1
    else:
        return dist

V,E = map(int,input().split())
G = defaultdict(list)
for i in range(E):
    u,v,d = map(int,input().split())
    G[u-1].append((v-1,-d))
d = bellman_ford(V,G,0)
if d==-1:
    print("inf")
else:
    print(-1*d[V-1])

Submission status: Accepted

Solution code:
def bellman_ford(x, V, E):
    V[x][0] = 0
    negative = [False for _ in range(len(V))]
    for i in range(len(V) - 2):
        for a, b, c in E:
            if V[b][0] > V[a][0] + c:
                V[b][0] = V[a][0] + c
                V[b][1] = a

    for a, b, c in E:
        if V[b][0] > V[a][0] + c:
            negative[b] = True
        elif negative[a]:
            negative[b] = True

    return V, negative

INF = 10 ** 15
n, m = map(int, input().split())
V = [[INF, 0] for _ in range(n + 1)]
E = []
for i in range(m):
    ai, bi, ci = map(int, input().split())
    E.append([ai, bi, -ci])
V, negative = bellman_ford(1, V, E)
if negative[n]:
    print('inf')
else:
    i = n
    ans = 0
    while(i != 1):
        d, i = V[i]
        ans += d
    print(-V[n][0])

Submission status: Accepted

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

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

vi=0
min_dis_list = [10**27 for i in range(N)]
min_dis_list[vi] = 0
prev_list = [-1 for i in range(N)]

for i in range(N-1):
    for e in e_list:
        u,v,d = e
        if min_dis_list[v]>min_dis_list[u]+d:
            min_dis_list[v]=min_dis_list[u]+d
            prev_list[v]=u

neg_loop_flag=[False for i in range(N)]

for i in range(N):
    for e in e_list:
        u,v,d = e
        if min_dis_list[u] + d < min_dis_list[v]:
            neg_loop_flag[v]=True
            min_dis_list[v] = min_dis_list[u] + d
        if neg_loop_flag[u]:
            neg_loop_flag[v]=True
        
if neg_loop_flag[N-1]:
    print("inf")
else:
    print(-min_dis_list[N-1])

Submission status: Accepted

Solution code:
# ABC 061 D
# 有向グラフ各辺のコストを集めて最大化する問題だが、全部符号を変えれば最短経路問題にできる

from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class BellmanFord(object):

    def __init__(self, v_len, edges, start):
        """
        隣接行列を使っていないので、有向グラフにのみ適用可能。
        ベルマンフォード法によって最短経路を求める。
        ダイクストラと違って負の数も扱えるが、O(|V||E|) なのでダイクストラより遅い。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: 辺のリスト
        :param start: 始点 単一視点最短経路問題として解くので必要
        """
        self._dist = [float('inf') for _ in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for _ in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(edges, start)

    def _solve(self, edges, start):
        self._dist[start] = 0

        cnt = 0
        while True:  # 更新は高々 |V| - 1 回で終わる
            cnt += 1
            updated = False
            for e in edges:
                if self._dist[e.src] + e.cost < self._dist[e.dst]:
                    self._dist[e.dst] = self._dist[e.src] + e.cost
                    self._prev[e.dst] = e.src
                    if cnt >= len(self._dist):
                        self._dist[e.dst] = float('-inf')
                    updated = True
            if not updated:
                break

    def distance(self, goal):
        """
        負の閉路を含む場合は -inf を返す。
        """
        return self._dist[goal]

    def path(self, goal):
        """
        負の閉路を含む場合は計算が終わらない。
        """
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N, M = map(int, input().split())
edges = list()
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, -1 * c))
bf = BellmanFord(N + 1, edges, 1)
print(-1 * bf.distance(N))