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:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

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

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)

#graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1

d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
#print(d1)
print(-int(d1[0][0]))

Submission status: Runtime Error

Solution code:
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())
 
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
#print(d)

def BELLMANFORD(point,d):
    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:
                    negative[nex]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1

    return cost,negative

x,y=(BELLMANFORD(1,d))
#print(x,y)
if y[n-1]==1:
    print("inf")
else:
    print(x[n])

Submission status: Runtime Error

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

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n+1)]
INF =  2000 * 10**10
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    edge[a-1].append([b-1,c])
edge[n-1].append([n, 0])

def dfs(prev, prev_c, v):
    if v == n:
        return 0
    max_cost = -INF
    for e in edge[v]:
        if e[0] == prev:
            if prev_c + e[1] > 0:
                max_cost = INF
            continue
        max_cost = max(max_cost, e[1] + dfs(v, e[1], e[0]))
    return max_cost

cost = dfs(-1, 0, 0)
if cost > INF // 2:
    print("inf")
else:
    print(cost)

Submission status: Runtime Error

Solution code:
n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n+1)]
INF =  2000 * 10**9
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    edge[a-1].append([b-1,c])
edge[n-1].append([n, 0])

def dfs(prev, prev_c, v):
    if v == n:
        return 0
    max_cost = -INF
    for e in edge[v]:
        if e[0] == prev:
            if prev_c + e[1] > 0:
                max_cost = INF
            continue
        max_cost = max(max_cost, e[1] + dfs(v, e[1], e[0]))
    return max_cost

cost = dfs(-1, 0, 0)
if cost > INF // 2:
    print("inf")
else:
    print(cost)

Submission status: Runtime Error

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # INF = float("inf")

    # 初期値用:十分小さい数(-100億)
    # -INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [INF]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if math.isinf(d[a[i]-1]):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[b[i]-1]+=1
                update=True
        if not update:
            break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    # negative = [False]*N
    # for j in range(N):
    #     for i in range(M):
    #         if(d[a[i]-1] == 1e10):
    #             continue
    #         if(d[b[i]-1] > d[a[i]-1]+c[i]):
    #             d[b[i]-1] = d[a[i]-1]+c[i]
    #             negative[b[i]-1] = True
    #         if(negative[a[i]-1]):
    #             negative[b[i]-1] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [1e10]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if(d[a[i]-1] == 1e10):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[i]+=1
                update=True
            if not update:
                break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    # negative = [False]*N
    # for j in range(N):
    #     for i in range(M):
    #         if(d[a[i]-1] == 1e10):
    #             continue
    #         if(d[b[i]-1] > d[a[i]-1]+c[i]):
    #             d[b[i]-1] = d[a[i]-1]+c[i]
    #             negative[b[i]-1] = True
    #         if(negative[a[i]-1]):
    #             negative[b[i]-1] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int n,m;
struct edge{ll from,to,cost;};
vector<edge> es;
ll d[MAX_T];
ll v,e;
bool BellmanFord(ll s){
    for(int i = 0; i < n; i++) d[i] = -INF;
    d[s] = 0;
    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < m; j++){
            edge e = es[j];
            if(d[e.from] != -INF && d[e.to] < d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    ll dn = d[n-1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            edge e = es[j];
            if(d[e.to] != -INF && d[e.to] < d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    if(d[n-1] > dn) return 0;
    else return 1;
}
//v = n,e = m;
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        es.push_back({a,b,c});
    }
    if(BellmanFord(0)) cout << d[n-1] << endl;
    else cout << "inf" << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1 and abci[1]=n-1:
                print('inf')
                exit()

print(-d[n-1])

Submission status: Runtime Error

Solution code:
inf = float('inf')

# distの初期化: dist = [inf for _ in range(N)]; dist[start] = 0
# True - >正常に更新, False -> 負閉路有り
def bellmanford(dist,edges,N):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                # 頂点数Nなら更新は高々N-1回で済む
                # N回目に更新を行うなら負閉路があるということ
                if i == N-1 nv == N-1:
                    return False
    return True

N,M = map(int,input().split())
info = []
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1; c = -c
    info.append((a,b,c))
 
dist = [inf for _ in range(N)]
dist[0] = 0

flag = bellmanford(dist,info,N)
ans = -dist[N-1] if flag is True else "inf"
print(ans)

Submission status: Runtime Error

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
negative=[]
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #負閉路の検出
    global negative
    negative=[False for i in range(num_v)]
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                negative[i]=True
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1 or negative[-1]:
    print("inf")
else:
    print(-ans[N])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
big=10**13
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
def dps(now,score,visited,ans):
    if now==N:
        ans=max(score,ans)
    for b,c in branch[now]:
        if ans>big:return ans
        if  b in visited:
            if score>big:continue
            else:ans=dps(a,float('inf'),visited,ans)
        else:
            ans=dps(b,score+c,visited|{now,},ans)
    return ans
ans=dps(1,0,set(),-1*float('inf'))
if ans>big:print('inf')
else:print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
big=10**13
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
def dps(now,score,visited,ans):
    if now==N:
        ans=max(score,ans)
    if len(branch[now])==0:
        return ans
    for b,c in branch[now]:
        if ans>big:return ans
        if  b in visited:
            return float('inf')
        ans=dps(b,score+c,visited|{now,},ans)
    return ans
ans=dps(1,0,set(),-1*float('inf'))
if ans>big:print('inf')
else:print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
big=10**13
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
def dps(now,score,visited,ans):
    if now==N:
        ans=max(score,ans)
    if len(branch[now])==0:
        return ans
    for b,c in branch[now]:
        if ans>big:return ans
        if  b in visited:
            return float('inf')
        ans=dps(b,score+c,visited|{now,},ans)
    return ans
print(dps(1,0,set(),-1*float('inf')))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
big=10**13
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
def dps(now,score,visited,ans):
    if now==N:
        ans=max(score,ans)
    for b,c in branch[now]:
        if ans>big:return ans
        if  b in visited:
            return float('inf')
        ans=dps(b,score+c,visited|{now,},ans)
    return ans
print(dps(1,0,set(),-1*float('inf')))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
def dps(now,score,visited,ans):
    if now==N:
        ans=max(score,ans)
    for b,c in branch[now]:
        if  b in visited:
            return 'inf'
        ans=dps(b,score+c,visited|{now,},ans)
    return ans
print(dps(1,0,set(),-1*float('inf')))

Submission status: Runtime Error

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

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated

d[G_ls[0][0]] = 0
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        if d[a] is None:
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Runtime Error

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

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated

d[G_ls[0][0]] = 0
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Runtime Error

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

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated

d[0] = 0
for m in range(M):
    is_updated = False
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if d[j] is None:
                if G[i][j] is not None:
                    d[j] = d[i] + G[i][j]
                    is_updated = True
                    continue
            if G[i][j] is not None:
              d[j], is_updated = update(d[j], d[i] + G[i][j], is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Runtime Error

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

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated

d[0] = 0
for m in range(M):
    is_updated = False
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if d[j] is None:
                if G[i][j] is not None:
                    d[j] = d[i] + G[i][j]
                    is_updated = True
                    continue
            if G[i][j] is not None:
              d[j], is_updated = update(d[j], d[i] + G[i][j], is_updated)
    if not is_updated:
        break
if is_updated:
    print(-1)
else:
    print(d[-1])

Submission status: Runtime Error

Solution code:
using ll = long long;
const ll INF = 1LL << 50;

#include <iostream>
using namespace std;
int main(){
    int N, M;
    cin >> N >> M ;

    const int NMAX = 1000;
    const int MMAX = 2000;
    int a[MMAX], b[MMAX];
    ll c[MMAX];

    for (int i = 0; i < M ; ++i){
        cin >> a[i] >> b[i] >> c[i];
        c[i] = -c[i];
    }

    ll dist[NMAX];

    for (int i = 0; i < N; ++i){
        dist[i] = INF;
    }

    dist[0] = 0;


    for (int loop = 0; loop < N-1; ++ loop){
        for (int i = 0; i < M; ++i){
            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];
            }
        }
    }

    ll ans = dist[N-1];

    bool negative[MMAX];

    for (int i = 0; i < N; ++i){
        negative[i] = false;
    }

    for (int loop = 0; loop < N; ++loop){
        for (int i = 0; i < M; ++i){
            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];
                negative[b[i]-1] = true;
            }

            if (negative[a[i]-1] == true){
                negative[b[i]-1] = true;
            }
        }
    }


    if (negative[N-1])
        cout << "inf" << endl;
    else
    {
        cout << -ans << endl;
    }
    return 0;
}

Submission status: Runtime Error

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

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

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

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

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
def dfs(a):
  if N in con[a]:
    return True
  if len(con[a])==0:
    return False
  tmp=False 
  for ch in con[a]:
    if dfs(ch):
      tmp=True 
      break
  return tmp
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        if dfs(a):
          print("inf")
          exit(0)

print(allcost[N])

Submission status: Runtime Error

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

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

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

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

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
def dfs(a):
  if N in con[a]:
    return True
  if len(con[a])==0:
    return False
  tmp=False 
  for ch in con[a]:
    if dfs(ch):
      tmp=True 
      break
  return tmp
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        if dfs(b):
          print("inf")
          exit(0)

print(allcost[N])

Submission status: Runtime Error

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]][i[1]] = [i[1], i[2]]
    else:
        rs[i[0]] = {i[1]: i[2]}

maxn = [float('inf') * -1] * (n + 1)
maxn[1] = 0 

inf_point = [False] * (n + 1)
nextr = [[1, i, {1}] for i in rs[1]]
while len(nextr) != 0:
    r = nextr.pop(0)
    if r[1] in r[2]:
        maxn[r[1]] = float('inf')
    elif r[1] in rs:
        nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]

nextr = [[1, i, {1}] for i in rs[1]]
while len(nextr) != 0:
    r = nextr.pop(0)
    maxn[r[1]] = max(maxn[r[1]], maxn[r[0]] + rs[r[0]][r[1]])
    if r[1] not in r[2] and r[1] in rs:
        nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]
print(maxn[n])

Submission status: Runtime Error

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]][i[1]] = [i[1], i[2]]
    else:
        rs[i[0]] = {i[1]: i[2]}

maxn = [float('inf') * -1] * (n + 1)
maxn[1] = 0 

inf_point = [False] * (n + 1)
nextr = [[1, i, {1}] for i in rs[1]]
while len(nextr) != 0:
    r = nextr.pop(0)
    if r[1] in r[2]:
        maxn[r[1]] = float('inf')
    elif r[1] in rs:
            nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]

nextr = [[1, i, {1}] for i in rs[1]]
while len(nextr) != 0:
    r = nextr.pop(0)
    maxn[r[1]] = max(maxn[r[1]], maxn[r[0]] + rs[r[0]][r[1]])
    if r[1] not in r[2] and r[1] in rs:
        nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]
print(maxn[n])

Submission status: Runtime Error

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]].append([i[1], i[2]])
    else:
        rs[i[0]] = [[i[1], i[2]]]

inf_point = [False] * (n + 1)
for _ in range(2):
    nextr = [[1, i[0], {1}] for i in rs[1]]
    while len(nextr) != 0:
        r = nextr.pop(0)
        setr = r[2]
        if r[1] in setr:
            inf_point[r[1]] = True
        else:
            if inf_point[r[0]]:
                inf_point[r[1]] = True
            setr.add(r[1])
            if r[1] in rs:
                nextr += [[r[1], i[0], setr] for i in rs[r[1]]]
if inf_point[n]:
    print('inf')
    sys.exit(0)

nextr = [[1, 0, {1}]]
maxn = float('inf') * -1
while len(nextr) != 0:
    ori = nextr.pop(0)
    if ori[0] == n:
        maxn = max(maxn, ori[1])

    if ori[0] in rs:
        for j in rs[ori[0]]:
            if j[0] in ori[2]:
                inf_point.add(j[0])
            else:
                d = ori[2].copy()
                d.add(j[0])
                nextr.append([j[0], ori[1] + j[1], d])
print(maxn)

Submission status: Runtime Error

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]].append([i[1], i[2]])
    else:
        rs[i[0]] = [[i[1], i[2]]]

inf_point = [False] * (n + 1)
for _ in range(2):
    nextr = [[1, i[0], {1}] for i in rs[1]]
    while len(nextr) != 0:
        r = nextr.pop(0)
        setr = r[2]
        if r[1] in setr:
            inf_point[r[1]] = True
        else:
            if inf_point[r[0]]:
                inf_point[r[1]] = True
            setr.add(r[1])
            if r[1] in rs:
                nextr += [[r[1], i[1], setr] for i in rs[r[1]]]
if inf_point[n]:
    print('inf')
    sys.exit(0)

nextr = [[1, 0, {1}]]
maxn = float('inf') * -1
while len(nextr) != 0:
    ori = nextr.pop(0)
    if ori[0] == n:
        maxn = max(maxn, ori[1])

    if ori[0] in rs:
        for j in rs[ori[0]]:
            if j[0] in ori[2]:
                inf_point.add(j[0])
            else:
                d = ori[2].copy()
                d.add(j[0])
                nextr.append([j[0], ori[1] + j[1], d])
print(maxn)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph import NegativeCycleError
from scipy.sparse import csr_matrix

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

path1 = csr_matrix((score, (start, goal)), shape=(n, n), dtype=int)
try:
    score = bellman_ford(path1, indices=0)
    print(-int(score[-1]))
except NegativeCycleError:
    print("inf")

Submission status: Runtime Error

Solution code:
import sys


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


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

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


inf = 10**15

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

    if not update:
        break

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

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

Submission status: Runtime Error

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

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


inf = 10**15

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

    if not update:
        break

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

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

Submission status: Runtime Error

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

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


inf = 10**15

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

    if not update:
        break
    elif i == N:
        ans = 'inf'

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