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: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		#will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			#if not upd8s[i]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					#will_upd8s[t] = True #更新した点だけ次に見る
		#upd8s = will_upd8s[:]
		if not upd8: break #なにも更新しなかったら終わり

	if upd8 == True: #N回ループしてまだ更新フラグ立ってる
		return -INF	#->負回路が存在する
	else:
		return Costs[Goal]


ans = BellmanFord(0,N-1)
if ans == -INF:
	print('inf')
else:
	print(-ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(N,lines,Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[i]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る
		upd8s = will_upd8s[:]
		if not upd8: break #なにも更新しなかったら終わり

	if upd8 == True: #N回ループしてまだ更新フラグ立ってる
		return -INF	#->負回路が存在する
	else:
		return Costs[Goal]


Start = 0
Goal = N-1
ans = BellmanFord(N,lines,Start,Goal)
if ans == -INF:
	print('inf')
else:
	print(-ans)

Submission status: Wrong Answer

Solution code:
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [-inf for f in range(num_v)]
    d[start] = 0;
    for i in range(20000):
        update = False
        for e in edge:
            if (d[e[0]-1] != -inf and d[e[1]-1] < d[e[0]-1] + e[2]):
                d[e[1]-1] = d[e[0]-1] + e[2]
                update = True
        if not update:
            break
    else:
      return "inf"
    return d[-1]
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
ans = shortest_path(p,n,0)
print(ans)

Submission status: Wrong Answer

Solution code:
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [-inf for f in range(num_v)]
    d[start] = 0;
    for i in range(6000):
        update = False
        for e in edge:
            if (d[e[0]-1] != -inf and d[e[1]-1] < d[e[0]-1] + e[2]):
                d[e[1]-1] = d[e[0]-1] + e[2]
                update = True
        if not update:
            break
    else:
      return "inf"
    return d[-1]
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
ans = shortest_path(p,n,0)
print(ans)

Submission status: Wrong Answer

Solution code:
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [-inf for f in range(num_v)]
    d[start] = 0;
    for i in range(4000):
        update = False
        for e in edge:
            if (d[e[0]-1] != -inf and d[e[1]-1] < d[e[0]-1] + e[2]):
                d[e[1]-1] = d[e[0]-1] + e[2]
                update = True
        if not update:
            break
    else:
      return "inf"
    return d[-1]
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
ans = shortest_path(p,n,0)
print(ans)

Submission status: Wrong Answer

Solution code:
class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    
    def __init__(self, N):
        self.N = N
        
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
        
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        while update:
            update = False
            cnt = cnt + 1
            if cnt > self.N + 1:
                return 'NegativeCycle'
            
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
                
        return D

    
V, E = list(map(int, input().split()))
bf = BellmanFord(V)
for i in range(E):
    frm, to, cost = list(map(int, input().split()))
    bf.add_edge(frm - 1, to - 1, -cost)
    

ans = bf.calcD(0)
if ans == 'NegativeCycle':
    print("inf")
else:
    print(-ans[V-1])

Submission status: Wrong Answer

Solution code:
class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    
    def __init__(self, N):
        self.N = N
        
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
        
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        while update:
            update = False
            cnt = cnt + 1
            if cnt > self.N:
                return 'NegativeCycle'
            
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
                
        return D

    
V, E = list(map(int, input().split()))
bf = BellmanFord(V)
for i in range(E):
    frm, to, cost = list(map(int, input().split()))
    bf.add_edge(frm - 1, to - 1, -cost)
    

ans = bf.calcD(0)
if ans == 'NegativeCycle':
    print("inf")
else:
    print(-ans[V-1])

Submission status: Wrong Answer

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

def bf(links, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    dj[st] = 0
    for i in range(N):
        updated = False
        for link in links:
            fn, tn, lc = link
            lc *= -1
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                updated = True
        if not updated: break
    else:
        return inf
    return -dj[-1]

links = []
for _ in range(M):
    links.append([int(x) for x in input().split()])

print(bf(links, N, 1))

Submission status: Wrong Answer

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

def bf(links, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    paths = dict((x, set([x])) for x in range(n + 1))
    dj[st] = 0
    while True:
        updated = False
        for link in links:
            fn, tn, lc = link
            lc *= -1
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                if tn in paths[fn]: return inf
                paths[tn] = paths[fn] | set([tn])
                updated = True
        if not updated: break
    return -dj[-1]

links = []
for _ in range(M):
    links.append([int(x) for x in input().split()])

print(bf(links, N, 1))

Submission status: Wrong Answer

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

def bf(adj, n, st=1):
    inf = float('-inf')
    dj = [inf] * (n + 1)
    paths = dict((x, set([x])) for x in range(n + 1))
    dj[st] = 0
    while True:
        updated = False
        for fn, x in adj.items():
            for y in x:
                tn, lc = y
                if dj[fn] + lc > dj[tn]:
                    dj[tn] = dj[fn] + lc
                    if tn in paths[fn]: return -inf
                    paths[tn] = paths[fn] | set([tn])
                    updated = True
        if not updated: break
    return dj[-1]

adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))

print(bf(adj, N, 1))

Submission status: Wrong Answer

Solution code:
import heapq
inf = -float('inf')
N, M = list(map(int, input().split()))
paths = [{} for i in range(N+1)]
for i in range(M):
    s,t,score = list(map(int, input().split()))
    paths[s][t] = score

def dijkstra(start, nodes, N):
    cost = [inf] * (N + 1)
    cost[start] = 0
    flg = [0 for i in range(N+1)]
    q = []
    heapq.heappush(q, (0, start))
    while q:
        w, x = heapq.heappop(q)
 #       print(x, "-", w)
        flg[x] += 1
        if flg[N] >= M:
            cost[N] = 'inf'
            break
        if cost[x] > w: continue
        for y in nodes[x]:
            if cost[x] + paths[x][y] > cost[y]:
                cost[y] = cost[x] + paths[x][y]
                heapq.heappush(q, (cost[y], y))
    return cost

S = dijkstra(1, paths, N)
#E = dijkstra(N, paths, N)

print(S[N])
#print(E)

Submission status: Wrong Answer

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

import heapq
def dijkstra(adj, n, st=1):
    inf = float('-inf')
    dj = [inf] * (n + 1)
    paths = dict((x, set([x])) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        fc *= -1
        if dj[fn] > fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc > dj[tn]:
                dj[tn] = dj[fn] + lc
                if tn in paths[fn]: return -inf
                paths[tn] = paths[fn] | set([tn])
                heapq.heappush(q, (-dj[tn], tn))
    return dj[-1]

adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))

print(dijkstra(adj, N, 1))

Submission status: Wrong Answer

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

import heapq
def dijkstra(adj, n, st=1):
    inf = float('-inf')
    dj = [inf] * (n + 1)
    paths = dict((x, set([x])) for x in range(n + 1))
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        fc *= -1
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc > dj[tn]:
                dj[tn] = dj[fn] + lc
                if tn in paths[fn]: return -inf
                paths[tn] = paths[fn] | set([tn])
                heapq.heappush(q, (-dj[tn], tn))
    return dj[-1]

adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))

print(dijkstra(adj, N, 1))

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]

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

for i in range(n):
    for a, b, c in es:
        x[b] = max(x[b], x[a]+c)

prevxn = x[n]
for a, b, c in es:
    if x[b] < x[a] + c:
        print('inf')
        exit()

print(x[n])

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    dist = defaultdict(lambda: sys.maxsize)
    pred = defaultdict(lambda: -1)

    dist[s] = 0

    N = len(V)
    for i in range(N+1):
        for u in g:
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if i == N:
                        return 'inf'
                    dist[v] = dist[u] + g[u][v]
                    pred[v] = u
    return dist


@mt
def slv(N, M, ABC):
    g = defaultdict(dict)
    g_ = defaultdict(dict)
    for a, b, c in ABC:
        g_[b][a] = c

    reachable = [N]
    q = [N]
    while q:
        v = q.pop()
        for u in g_[v]:
            if u not in reachable:
                reachable.append(u)
                q.append(u)
    reachable = set(reachable)
    for a, b, c in ABC:
        if a in reachable and b in reachable:
            g[a][b] = -c

    dist = BellmanFord(g, 1)
    if dist == 'inf':
        return 'inf'
    return -1*min(dist.values())


def main():
    N, M = read_int_n()
    ABC = [read_int_n() for _ in range(M)]

    print(slv(N, M, ABC))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
inf_flg = False 

for i in range(N * 2) :
    break_flg = True 
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c and not(cost[t] == cost[f] == INF):
            break_flg = False 
            cost[t] = cost[f] + c
            
            if i >= N and t == N - 1:
                inf_flg = True 
                break
        
        if break_flg == True :
            break
    
if inf_flg == True :
    print("inf")
else :
    for c in cost :
        if c == INF :
            print("")
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
inf_flg = False 

for i in range(N * 2) :
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c and not(cost[t] == cost[f] == INF):
            cost[t] = cost[f] + c
            
            if i >= N :
                inf_flg = True 
    
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

for i in range(N) :
    # break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            # break_flg = False
            
        if i == N - 1 and t == N - 1 :
            inf_flg = True 
            
    # break flg
    # if break_flg == True :
    #    break
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

for i in range(N) :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
        if i == N - 1 and t == N - 1 :
            inf_flg = True 
            
    # break flg
    if break_flg == True :
        break
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

for i in range(N) :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
    # break flg
    if break_flg == True :
        break
    
    # infinity flg 
    if i == N - 1 :
        inf_flg = True
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

while True :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
    if break_flg == True :
        break
    
    if cnt > N :
        inf_flg = True
        break
    
    cnt += 1
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    paths.append(list(map(int, input().split())))
    
INF = -10**20
cost = [INF for x in range(N)]
cost[0] = 0
break_flg, inf_flg = True, False
cnt = 0

while True :
    break_flg = True 
    
    for p in paths :
        f, t, c = p[0] - 1, p[1] - 1, p[2]
        
        if cost[t] < cost[f] + c :
            cost[t] = cost[f] + c
            break_flg = False
            
    if break_flg == True :
        break
    
    if cnt >= N :
        inf_flg = True
        break
    
    cnt += 1
        
if inf_flg == True :
    print("inf")
else :
    print(cost[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, -c])
    
# go
INF = 10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] > nodes[p[0]] + p[2] :
            nodes[p[1]] = min(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
            
    cnt += 1
            
    if toBreak == True or cnt > N :
        break
        
if cnt > N :
    print("inf")
else :
    print(-nodes[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, c])
    
# go
INF = -10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] < nodes[p[0]] + p[2] :
            nodes[p[1]] = max(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
            cnt += 1
            
    if toBreak == True or cnt > M:
        break
        
if cnt > N * M :
    print("inf")
else :
    print(nodes[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, c])
    
# go
INF = -10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] < nodes[p[0]] + p[2] :
            nodes[p[1]] = max(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
            
    cnt += 1
    if toBreak == True or cnt > N * M:
        break
        
if cnt > N * M :
    print("inf")
else :
    print(nodes[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, c])
    
# go
INF = -10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] < nodes[p[0]] + p[2] :
            nodes[p[1]] = max(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
        cnt += 1
            
    if toBreak == True or cnt > N * M:
        break
        
if cnt > N * M :
    print("inf")
else :
    print(nodes[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, c])
    
# go
INF = -10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] < nodes[p[0]] + p[2] :
            nodes[p[1]] = max(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
            cnt += 1
            
    if toBreak == True or cnt > N * M:
        break
        
if cnt > N * M :
    print("inf")
else :
    print(nodes[N - 1])

Submission status: Wrong Answer

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

for i in range(M) :
    a, b, c = map(int, input().split())
    paths.append([a - 1, b - 1, c])
    
# go
INF = -10**20
nodes = [INF for x in range(N)]
nodes[0] = 0

toBreak = True
cnt = 0

while True :
    toBreak = True
    for p in paths :
        if nodes[p[1]] < nodes[p[0]] + p[2] :
            nodes[p[1]] = max(nodes[p[0]] + p[2], nodes[p[1]])
            toBreak = False 
            cnt += 1
            
    if toBreak == True or cnt >= N * M:
        break
        
if cnt >= N * M :
    print("INF")
else :
    print(nodes[N - 1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7

N,M = map(int,input().split())
lines = defaultdict(set)

for i in range(M):
	a,b,c = list(map(int,input().split())) #a -> b コスト:c の経路
	lines[a-1].add((b-1,-c))

#lines(dd),N(ノード数),s->tの最短orINFを返す
def BellmanFord(lines,N,s,t):
	weight = [INF]*N
	weight[s] = 0
	count = 0
	while True:
		flag = False
		prev = weight[t]
		for i in range(N):
			for t,c in list(lines[i]):
				if weight[t] > weight[i]+c :
					weight[t] = weight[i]+c
					flag = True

		if not flag:
			return weight[t]
			break

		if count == N+2:
			if prev != weight[t]:
				return INF
			else:
				return weight[t]

		count += 1

ans = BellmanFord(lines,N,0,N-1)
if ans != INF:
	ans *= -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7

N,M = map(int,input().split())
lines = defaultdict(set)

for i in range(M):
	a,b,c = list(map(int,input().split())) #a -> b コスト:c の経路
	lines[a-1].add((b-1,-c))

def BellmanFord(lines,N,s):
	weight = [INF]*N
	weight[s] = 0
	count = 0
	while True:
		flag = False
		for i in range(N):
			for t,c in list(lines[i]):
				if weight[t] > weight[i]+c :
					weight[t] = weight[i]+c
					flag = True

		if not flag:
			return weight[N-1]
			break

		if count == N+2:
			return INF

		count += 1

ans = BellmanFord(lines,N,0)
if ans != INF:
	ans *= -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7

N,M = map(int,input().split())
lines = defaultdict(set)

for i in range(M):
	a,b,c = list(map(int,input().split())) #a -> b コスト:c の経路
	lines[a-1].add((b-1,-c))

def BellmanFord(lines,N,s):
	weight = [INF]*N
	weight[s] = 0
	count = 0
	while True:
		flag = False
		for i in range(N):
			for t,c in list(lines[i]):
				if weight[t] > weight[i]+c :
					weight[t] = weight[i]+c
					flag = True

		if not flag:
			return weight[N-1]
			break

		if count == N:
			return INF

		count += 1

ans = BellmanFord(lines,N,0)
if ans != INF:
	ans *= -1
print(ans)

Submission status: Wrong Answer

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

INF = 2 << 40
G, dist = [None for i in range(M)], [INF for j in range(N)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(2*N):
        for j in range(M):
            e = G[j]
            if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i >= N - 1 and e.t == N - 1 or e.f == N - 1:
                    return True

    return False


def main():
    for i in range(M):
        a, b, c = map(int, input().split())
        G[i] = Edge(a-1, b-1, -c)

    c = bellman_ford(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

INF = 2 << 40
G, dist = [None for i in range(M)], [INF for j in range(N)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(N):
        for j in range(M):
            e = G[j]
            if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i == N - 1:
                    return True

    return False


def main():
    for i in range(M):
        a, b, c = map(int, input().split())
        G[i] = Edge(a-1, b-1, -c)

    c = bellman_ford(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

INF = 2 << 40
G = [[] for i in range(N)]
dist = [INF for j in range(N)]


def bellman_ford(s):
    p, flg = [-1 for i in range(N)], [False for i in range(N)]
    dist[s], flg[s], cnt = 0, True, 0

    while True:
        if cnt >= 2 * N:
            return False

        on = []
        for i in range(N):
            if flg[i]:
                on.append(i)
                flg[i] = False

        if len(on) == 0:
            return True

        for i in on:
            for j in G[i]:
                if dist[i] + j[1] < dist[j[0]]:
                    dist[j[0]] = dist[i] + j[1]
                    p[j[0]], flg[j[0]] = i, True

        cnt += 1


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

    check = bellman_ford(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''using hint'''
N,M =map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(M)]
abc = [(a-1,b-1,-c) for a,b,c in abc]

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

for _ in range(N-1):
    for a,b,c in abc:
        if dist[a] == float('inf'):
            continue
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

ans = dist[N-1]
negative = [False]*N

for _ in range(N):
    for a,b,c in abc:
        if dist[a] == float('inf'):
            continue
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            negative[b] = True
            negative[N-1] = True
            break
        if negative[a]:
            negative[b] = True
    if negative[N-1]:
        break

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

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
ABC = (map(int, input().split()) for i in range(M))

inf = float("inf")
dist = [inf]*N
dist[0] = 0 
negative = [0]*N

for i in range(N):
    for a,b,c in ABC:
        a -= 1
        b -= 1
        c = -c
        if dist[a] != inf and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i == N-1 and b == N-1:
                print('inf')
                sys.exit()

print(-dist[-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c])
inf=10**30
dist=[inf]*N
dist[0]=0
for i in range(M+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==M:
            print('inf')
            sys.exit()
print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c])
inf=10**20
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==N:
            print('inf')
            sys.exit()
print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c])
inf=10**20
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            continue
        dist[y]=dist[x]+z
        if i==N-1:
            print('inf')
            sys.exit()
print(-dist[N-1])