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: Runtime Error

Solution code:
from pprint import pprint

def bellman_ford(V, E, s):
    """ 始点sから残りのノードへの最短経路を求めるベルマンフォード法
    :param V: 頂点数
    :param E: (ノード1, ノード2, コスト)のタプルのリスト
    :param s: 始点とするノード
    :return : (距離リスト, 最短経路, 負の辺によるループが存在するか)a
    """
    ##### 前処理 #####
    from collections import defaultdict
    # INFの定義
    INF = -10 ** 10
    # 最短経路情報を格納する辞書
    dist = defaultdict(lambda: INF) # 始点から始点への移動コスト
    dist[s] = 0
    # 移動経路の履歴
    pre = {}

    ##### 最短経路算出 #####
    # 高々|V|-1回の探索でいい(|V|回以上更新がある場合は負の閉路が存在)
    for _ in range(V-1):
        for n1, n2, w in E:
            # 始点からi回の探索でたどり着けない頂点は考慮しない
            # 始点 -> n2 までの最短距離 > 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト
            # の場合より短い経路が発見できたと言うことなので情報を更新
            if dist[n1] != INF and dist[n2] < dist[n1] + w:
                dist[n2] = dist[n1] + w
                pre[n2] = n1

    ##### 負の閉路検出 #####
    is_cycle = False
    for n1, n2, w in E:
        # 正しい最短距離が求まったと仮定(重要)
        # 始点 -> n1 までの最短距離 + n1 -> n2 への移動コスト < 始点 -> n2 までの最短経路
        if dist[n1] + w < dist[n2]:
            is_cycle = True

    return (dist, pre, is_cycle)

def main():
    E = []
    # グラフの頂点数
    n,m = map(int,input().split())
    # 辺情報
    for _ in range(m):
        a,b,c = map(int,input().split())
        E.append((a,b,c))
    #始点
        s = 1

    # ベルマンフォードる
    dist, pre, is_cycle = bellman_ford(n, E, 1)
"""
    # 出力
    print()
    print('##### GRAPH1 (負の閉路なし) #####')
    print('===== start node =====')
    print(s)
    print()
    print('===== dist =====')
    pprint(dist)
    print()
    print('===== pre =====')
    pprint(pre)
    print()
    print('===== is_cycle =====')
    print(is_cycle)
    print('#################################')
    print()
"""
    if is_cycle:
        print(max(dist.values()))
    else:
        print('inf')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = {}
while cur != 0:
    root.add(cur)
    cur = before_ls[cur]
root.add(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

Submission status: Runtime Error

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
dist = floyd_warshall(cost)
# print(int(-1 * dist[0][n-1]))
print('inf')

Submission status: Runtime Error

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

cost = [[float('inf')] * n for _ in range(n)]
for a, b, c in abc:
    cost[a-1][b-1] = -c

from scipy.sparse.csgraph import floyd_warshall
dist = floyd_warshall(cost)
print(int(round(-1 * dist[0][n-1])))

Submission status: Runtime Error

Solution code:
def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance.copy()
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True

        if not update or loop_cnt > n: break
    return d

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

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] != test[n-1]:
    print("inf")
else :
    print(-dist[n-1])

Submission status: Runtime Error

Solution code:
def bellman_ford(n, edges, s):
    d = [float('inf')] * n
    d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        
        if not update or loop_cnt >= n: break
    return d, (loop_cnt >= n)

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

dist, cycle = bellman_ford(n, edges, 0)
if cycle:
    print("inf")
else :
    print(dist[n])

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1].append((b-1, -c))
    
    
#ベルマンフォード法:負閉路の検出とある一点から他のすべての点への最短距離の算出

def BellmanFord(E, N, M, source):
    #E:E[a]は頂点aを始点とする辺のリストであり、辺の終点bと辺の重みwが(b, w)の形で格納されている
    #N:頂点の数
    #M:辺の数
    #source:始点
    #グラフの初期化
    inf = 10**15
    d = [inf for i in range(N)]
    d[source] = 0
    
    #辺の緩和
    for i in range(N):
        for j in range(M):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and j == N-1: return -1
    
    return d

dist = BellmanFord(E, N, M, 0)
if dist == -1:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Runtime Error

Solution code:
INF = 10**18

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

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

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                if _==N-1:
                    update = adj
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    visited = [0 for _ in range(N)]
    visited[update] = 1
    stack = [update]
    while stack:
        node = stack.pop()
        for adj in graph[node][0]:
            if not visited[adj]:
                visited[adj] = 1
                stack.append(adj)
    if visited[N-1]:
        print('inf')
    else:
        print(-dist[N-1])

Submission status: Runtime Error

Solution code:
INF = 10**18

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

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

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                if _==N-1:
                    update = adj
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    visited = [0 for _ in range(N)]
    visited[adj] = 1
    stack = [adj]
    while stack:
        node = stack.pop()
        for adj in graph[node][0]:
            if not visited[adj]:
                visited[adj] = 1
                stack.append(adj)
    if visited[N-1]:
        print('inf')
    else:
        print(-dist[N-1])

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
mINF = -(10**16)
n,m = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i], B[i], C[i] = a-1, b-1, -c

graph = [[mINF]*n for i in range(n)]
for i in range(m) :
    graph[A[i]][B[i]] = C[i]

graph = csgraph_from_dense(graph, null_value=mINF)
try :
    dist = bellman_ford(graph)
    print(-dist[0][n-1])
except : # NegativeCycleError in scipy
    ans = "inf"

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define ALLTRUE(xs) all_of(ALL(xs),[](bool x){return x;})
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define ANYTRUE(xs) any_of(ALL(xs),[](bool x){return x;})
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

struct edge { int to,cost; };
struct ftedge { int from,to,cost; };
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VECINT;
typedef vector<ll> VECLL;

ll bellman_ford(int V, int s, vector<ftedge> es) {
  vector<ll> d(V,LLONG_MIN);d[s]=0;
  REP(i,V) {
    for (ftedge e:es) {
      if (d[e.from]!=INT_MIN && d[e.to]<d[e.from]+e.cost) {
        d[e.to] = d[e.from]+e.cost;
        if (i==V-1) return LLONG_MAX;
      }
    }
  }
  return d[V-1];
}

int main() {
  int N,M;cin>>N>>M;
  vector<ftedge> es;
  REP(i,M) {
    int a,b,c;cin>>a>>b>>c;
    a--;b--;
    es.push_back({a,b,c});
  }
  ll ans = bellman_ford(N,0,es);
  ans==LLONG_MAX ? OUT("inf") : OUT(ans);

  return 0;
}

Submission status: Runtime Error

Solution code:
# Python program to print all paths from a source to destination. 
cnt=0 
ans=0 
from collections import defaultdict 
from collections import Counter 
def check(arr): 
    #print(arr)
    ans=0 
    for i in range(1,len(arr)):
        ans+=e[(arr[i-1],arr[i])]
   # print(ans)
    return ans 
maxi=-10**1999  
mini=10**9 
#    sents a directed graph 
# using adjacency list representation 
class Graph: 

	def __init__(self,vertices): 
		#No. of vertices 
		self.V= vertices 
		
		# default dictionary to store graph 
		self.graph = defaultdict(list) 

	# function to add an edge to graph 
	def addEdge(self,u,v): 
		self.graph[u].append(v) 
	def printAllPathsUtil(self, u, d, visited, path):
	   
		# Mark the current node as visited and store in path 
		visited[u]= True
		path.append(u) 
		global ans 
		global maxi
		# If current vertex is same as destination, then print 
		# current path[] 
		if u ==d: 
		   # print(path)
		    if check(path): 
		        maxi=max(maxi,check(path))
		else: 
			# If current vertex is not destination 
			#Recur for all the vertices adjacent to this vertex 
			for i in self.graph[u]: 
				if visited[i]==False: 
					self.printAllPathsUtil(i, d, visited, path) 
					
		# Remove current vertex from path[] and mark it as unvisited 
		path.pop() 
		visited[u]= False


	# Prints all paths from 's' to 'd' 
	def printAllPaths(self,s, d): 

		# Mark all the vertices as not visited 
		visited =[False]*(self.V) 

		# Create an array to store paths 
		path = [] 

		# Call the recursive helper function to print all paths 
		self.printAllPathsUtil(s, d,visited, path) 



# Create a graph given in the above diagram 
n,m=map(int,input().split())
g = Graph(n)
e={}
from collections import defaultdict
di=defaultdict(list)
for i in range(m): 
    a,b,c=map(int,input().split())
    g.addEdge(a-1,b-1)
    e[(a-1,b-1)]=c 
    a-=1 
    b-=1 
    di[a].append(b)
    #g.addEdge(b-1,a-1)

s=0 
d=n-1 
q=[n-1]
vis=[0]*n 
vis[n-1]=1 
while q:
    t=q.pop(0)
    for i in di[t]:
        if not vis[i]:
            q.append(i)
            vis[i]=1 
f=1 
if vis[0]:
    f=0 
g.printAllPaths(s, d) 
print(maxi if f else 'inf')

Submission status: Runtime Error

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 1300: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))

Submission status: Runtime Error

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 3000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))

Submission status: Runtime Error

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(-int(d1[N]))

Submission status: Runtime Error

Solution code:
# D - Score Attack
import sys
sys.setrecursionlimit(10 ** 9)

import numpy as np
from heapq import heappush, heappop

N, M, = map(int, input().split())
graph = [[] for _ in range(N+1)] # graph[0]は使わない

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, -c)) # ヒープ構造を使うため重みはマイナスの値

def dijkstra(start, co):
    INF = float('inf')
    dist = [INF] * (N+1) # dist[0]は使わない
    dist[start] = 0
    que = [(0, start, co)] # queではscoreを先頭に
    while que:
        score, place, count = heappop(que) # placeは現在地
        if score > dist[place] or count > 2000: # 前来た時より点数が悪いか、無限ループしている場合continue
            continue
        for next_node, weight in graph[place]:
            score2 = score + weight
            if next_node == N and count > 1000: # いくらでも大きくなる場合
                print('inf')
                exit()
            if dist[next_node] > score2: # 点数が良くなるなら、データを更新
                dist[next_node] = score2
                heappush(que, (score2, next_node, count+1))
    return dist

d1 = np.array(dijkstra(1, 0))
print(int(-d1[N]))

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,m = MAP()
E = [[(0,0,0)]for i in range(m)]
for i in range(m):
    a,b,cost = MAP()
    E[i] = (a-1, b-1, -1*cost)



def bellmanford(s, E): #無向グラフの時はEに双方向から辺を追加
    d = [INF]*n
    d[s] = 0
    for i in range(n-1):
        for e in E:
            if d[e[0]] != INF and d[e[0]]+e[2] < d[e[1]]:
                d[e[1]] = d[e[0]]+e[2]
    return d

def find_negative_loop(s,E):
    d = bellmanford(s, E)
    negative = [False]*n
    for i in range(n):
        for j in range(m):
            if d[E[j][0]] != INF and d[E[j][0]]+E[j][2] < d[E[j][1]]:
                d[E[j][1]] = d[E[j][0]]+E[j][2]
                negative[j] = True
            if negative[E[j][0]]:
                negative[E[j][1]] = True

    return negative[n-1]

res = bellmanford(0,E)
if find_negative_loop(0,E):
    print('inf')
else:
    print(res[n-1]*-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
INF = 10**12
edges = [tuple(map(int, input().split())) for _ in range(M)]
dp = [-INF] * (N+1)
cnt = 0
dp[1] = 0
while True:
  update = False
  for a, b, c in edges:
    a, b, c = edges[i]
    if dp[a] != -1 and dp[b] < dp[a] + c:
      dp[b] = dp[a] + c
      update = True
      cnt += 1
  if update:
    if cnt == N-1:
      print('inf')
      exit()
  else:
    break
print(dp[N])

Submission status: Runtime Error

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

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

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N-1]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

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


main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    d = [[float('inf')] * N for _ in range(N)]
    edges = []
    
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edges.append([a,b,c])

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

    for i in range(N-1):
        for edge in edges:
            d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

    ans = d[N]
    for edge in edges:
        d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])

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


    

    
main()

Submission status: Runtime Error

Solution code:
def solve():
    global dp
    while True:
        flag = False
        for i in range(M):
            if dp[graph[i].f] + graph[i].cost > dp[graph[i].to] and dp[graph[i].f] != -float("inf"):
                dp[graph[i].to] = dp[graph[i].f] + graph[i].cost
                flag = True
        if not flag :
            break
def check_p_roop():
    d = [0 for i in range(N)]
    for i in range(N):
        for j in range(M):
            if d[graph[j].f] + graph[j].cost > d[graph[j].to] :
                d[graph[j].to] = d[graph[j].f] + graph[j].cost
                if i == N - 1 :
                    return True
    return False


if __name__ == '__main__':
    N, M = map(int, input().split())
    dp = [-float("inf") for i in range(N)]
    dp[0] = 0
    graph = [0 for _ in range(N)]
    class Edge:
        def __init__(self, f, to, cost):
            self.f = f
            self.to = to
            self.cost = cost
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = Edge(a-1, b-1, c)

    if check_p_roop():
        print("inf")
    else :
        solve()
        print(dp[N-1])

Submission status: Runtime Error

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

dp = [-10**9-1 for i in range(N)]
dp[0] = 0
visited = [False]*(N)
def search(now,visited):
    if now==(N-1) and len(graph[now]) == 0 :
        return
    else :
        visited[now] = True
        for i in graph[now]:
            if visited[i[0]]:
                if dp[i[0]] < dp[now]+i[1]:
                    dp[N-1] = float('inf')
                    return
                else :
                    continue
            else :
                dp[i[0]] = max(dp[i[0]],dp[now]+i[1])
                return search(i[0],visited)
search(0,visited)
print(dp[N-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split());a,b=[list(map(int,input().split()))for i in range(n)],[float("INF")]*(n+1);b[1]=0
for i in range(1,n+1):
    for s,t,u in a:
        if b[t]>b[s]-u:
            b[t]=b[s]-u
            if i==n and t==n:print("inf");exit()
print(-b[-1])

Submission status: Runtime Error

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            # print ('B')
            path = restore(N)
            # print (path)
            update = False
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[i] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        # print ('A')
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True

#呼び出しスタート地点を入れる
if shortest_path(1):
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Submission status: Runtime Error

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            # print ('B')
            path = set(restore(N))
            # print (path)
            update = False
            for i in range(M): #無向グラフのときは辺は実質的には2倍
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[i] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        # print ('A')
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True

#呼び出しスタート地点を入れる
if shortest_path(1):
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Submission status: Runtime Error

Solution code:
"""
Bellman-Ford
始点と終点が決められているとき、
経由する閉路のみを確認する必要がある。
"""
def Bellman_Ford2(g,start,goal):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    a0 = float("inf")
    for i in range(2*n):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                if i < n:
                    dist[to] = dist[v] + cost
                else:
                    dist[to] = -float("inf")
                updated = True
        if not updated: break
    if dist[goal] == -float("inf"): return None, False
#    if negative[-1]: return None, False
    return dist, True
 

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m,p = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    a,b,c = [int(i) for i in readline().split()]
    g[a-1].append((b-1,-c))
#    g[b-1].append((a-1,c))

dist, TF = Bellman_Ford2(g,0,-1)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())
link = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    link[a-1].append([b-1, c])
visited = [0] * N
ans = 0

#全ての頂点からループしてないか確かめるといけないかな？
def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**12)

N, M = map(int, input().split())
link = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    link[a-1].append([b-1, c])
visited = [0] * N
ans = 0

#全ての頂点からループしてないか確かめるといけないかな？
def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)

Submission status: Runtime Error

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

dist[0] = 0

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

ans = dist[N-1]

nega = [0] * 1000

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

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

Submission status: Runtime Error

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

dist[0] = 0

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

ans = dist[N-1]

nega = [0] * N

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

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