Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])


dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i >= n-1 and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n*2:
        break
print(-dist[-1])

Submission status: Accepted

Solution code:
ai_ = lambda: [int(x)-1 for x in input().split()]
ai = lambda: list(map(int, input().split()))

n,m = ai()

from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
    a,b,c = ai()
    edge[a-1].append([b-1, -c])

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

for i in range(n):
    for cur_v in range(n):
        for v, c in edge[cur_v]:
            if dist[v] > dist[cur_v] + c:
                dist[v] = dist[cur_v] + c
                if i == n-1 and v == n-1:
                    print('inf')
                    exit()
print(-dist[-1])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
infinite = -10**14
score = [infinite for _ in range(n+1)]
score[1] = 0
routes = [[] for _ in range(n+1)]
for i in range(m):
    ai, bi, ci = list(map(int, input().split()))
    routes[ai].append([bi, ci])
#print(routes)

is_inf = True
for r in range(n+2): 
    rev = 0
    for i in range(1,n+1):
        for (to, sc) in routes[i]:
            if score[to] < score[i] + sc:
                score[to] = score[i] + sc
                if to == n:
                    rev += 1
    if rev == 0 and r > n:
        is_inf = False
        break
            
if is_inf:
    print('inf')
else:
    print(score[n])

Submission status: Accepted

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

d = [-10**13 for i in range(n)]
d[0] = 0
flag = [0 for i in range(n)]
flag[0] = 1
d2 = [-10**13 for i in range(n)]
d2[0] = 0
flag2 = [0 for i in range(n)]
flag2[0] = 1

for i in range(n):
    for j in range(m):
        if flag[x[j][0] - 1]:
            d[x[j][1] - 1] = max(d[x[j][1] - 1], d[x[j][0] - 1] + x[j][2])
            flag[x[j][1]-1] = 1

for i in range(2*n+1):
    for j in range(m):
        if flag2[x[j][0] - 1]:
            d2[x[j][1] - 1] = max(d2[x[j][1] - 1], d2[x[j][0] - 1] + x[j][2])
            flag2[x[j][1] - 1] = 1

if d2[n-1] > d[n-1]:
    print("inf")
else:
    print(d[n-1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
es = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,cost in es:
        fr,to = fr-1,to-1
        cost *= -1
        if d[fr] != INF and d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1 and to == N-1:
                print('inf')
                exit()
print(-d[-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,m = li()

# graph
adj_list = [[] for _ in range(n)]

for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    adj_list[a].append((c,b))

# bellman-ford
INF = -10**15
dist = [INF]*n
dist[0] = 0
for j in range(n+1):
    for i in range(n):
        updated = False
        for cost, nex in adj_list[i]:
            bef = dist[nex]
            dist[nex] = max(dist[nex], dist[i]+cost)
            if bef != dist[nex]:
                updated = True
        
    if j == n-1:
        dis_j1 = dist[n-1]
        
    if j == n:
        dis_j = dist[n-1]
        
if dis_j1 != dis_j:
    print("inf")
else:
    print(dis_j)

Submission status: Accepted

Solution code:
INF = float('inf')
N,M = map(int,input().split())
edge = []
d = [INF]*N
d[0] = 0
negative = [False for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,-c])

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        d[edge[j][1]] = min(d[edge[j][1]],d[edge[j][0]]+edge[j][2])

ans = d[N-1]

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        if d[edge[j][1]]>d[edge[j][0]]+edge[j][2]:
            d[edge[j][1]]=d[edge[j][0]]+edge[j][2]
            negative[edge[j][1]] = True
        if negative[edge[j][0]]:
            negative[edge[j][1]] = True
print('inf' if negative[N-1] else -ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            if not negative[b]:
                update = True
            negative[b] = True
        if negative[a] and not negative[b]:
            negative[b] = True
            update = True
    if not update:
        break
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    ansn_1 = neg
    ans_n = neg
    
    for i in range(n+1):
        for frm, node in enumerate(graph):
            for cost, to in node:
                dist[to] = max(dist[to], dist[frm] + cost)
        
        if i == n-1:
            ansn_1 = dist[-1]
        elif i == n:
            ans_n = dist[-1]
            
    if ansn_1 != ans_n:
        return "inf"
    else:
        return ans_n
        

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    cur = neg
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for frm, node in enumerate(graph):
            for cost, to in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdate = True
        
        if cnt == n-1:
            cur = dist[-1]
            
        if cnt == n:
            if dist[-1] == cur:
                return dist[-1]
            else:
                return "inf"
        
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


def bf(graph: list):
    neg = -10**16
    n = len(graph)
    dist = [neg]*n
    dist[0] = 0
    
    hasUpdate = True
    cnt = 0
    cur = neg
    while hasUpdate:
        hasUpdate = False
        cnt += 1
        
        for frm, node in enumerate(graph):
            for cost, to in node:
                bef = dist[to]
                dist[to] = max(dist[to], dist[frm] + cost)
                
                # 更新されたならupdateをTrueに
                if dist[to] != bef:
                    hasUpdate = True
        
        if cnt == n:
            cur = dist[-1]
            
        if cnt == n+1:
            if dist[-1] == cur:
                return dist[-1]
            else:
                return "inf"
        
    return dist[-1]
                

n,m = li()

graph = [[] for _ in range(n)]
for i in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    
ans = bf(graph)
print(ans)

Submission status: Accepted

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


class BellmanFord(object):
    def __init__(self, edges, n_nodes, start):
        self.edges = edges
        dist = [float('inf')] * n_nodes
        dist[start] = 0
        prev = [None] * n_nodes

        for _ in range(n_nodes - 1):
            for u, v, weight in edges:
                if dist[u] == float('inf'):
                    continue
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
        self.dist = dist
        self.prev = prev

    def check(self, goal=None):
        if goal is None:
            for u, v, weight in self.edges:
                if self.dist[v] > self.dist[u] + weight:
                    return False
            return True
        else:
            negative = [False] * N
            for _ in range(N):
                for u, v, weight in self.edges:
                    if self.dist[u] == float('inf'):
                        continue
                    if negative[u] or self.dist[v] > self.dist[u] + weight:
                        negative[v] = True
            return not negative[goal]


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

bf = BellmanFord(edges, N, 0)
if bf.check(N - 1):
    print(-bf.dist[N - 1])
else:
    print('inf')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
inf=float("inf")
l=[tuple(map(int,input().split())) for i in range(m)]
 
d=[inf]*n
d[0]=0

for i in range(n):
  for a,b,c in l:
    a,b,c=a-1,b-1,-c
    if d[a]!=inf and d[b]>d[a]+c:
      d[b]=d[a]+c
      if i==n-1 and b==n-1:
        print("inf")
        exit()
print(-d[-1])

Submission status: Accepted

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(2*N): #2N回ループ(負回路の検出までみる)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る

		if not upd8: #なにも更新しなかったら終わり
			return Costs[Goal]

		if i == N-1: #Nループ目のGoalのCostを記録
			tmp = Costs[Goal]

		upd8s = will_upd8s[:]

	if tmp != Costs[Goal]:
		return -INF
	else:
		return Costs[Goal]

print(-BellmanFord(0,N-1))

Submission status: Accepted

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[s]: 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:
			return Costs[Goal] #なにも更新しなかったら終わり
	else: #負回路の検出(もうN回)
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print(-BellmanFord(0,N-1))

Submission status: Accepted

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:
			return Costs[Goal] #なにも更新しなかったら終わり
	else: #負回路の検出(もうN回)
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print(-BellmanFord(0,N-1))

Submission status: Accepted

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(3000):
        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 (e[1] == n and i >= n):
                  return "inf"
        if not update:
            break
    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: Accepted

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
        flag = False
        while update:
            cnt = cnt + 1
            if cnt > self.N:
                return D if flag == False else 'NegativeCycle'
            update = False
            flag = False
            
            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
                flag = flag | (to == self.N-1)
                
        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: Accepted

Solution code:
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Submission status: Accepted

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 _ in range(N):
        updated = False
        for link in links:
            fn, tn, lc = link
            if dj[fn] + lc > dj[tn]:
                dj[tn] = dj[fn] + lc
                updated = True
        if not updated: break
    else:
        negative = [False] * (n + 1)
        for _ in range(N):
            for link in links:
                fn, tn, lc = link
                negative[tn] |= negative[fn]
                if dj[fn] + lc > dj[tn]:
                    dj[tn] = dj[fn] + lc
                    negative[tn] = True
        if negative[N]: 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: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
E = [[] for i in range(N)]
revE = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, -c])
  revE[b - 1].append(a - 1)
revG = [False] * N
revG[-1] = True
Q = []
heapq.heappush(Q, N - 1)
while Q:
  s = heapq.heappop(Q)
  for adj in revE[s]:
    if not revG[adj]:
      revG[adj] = True
      heapq.heappush(Q, adj)
D = [N * 10 ** 9 + 1] * N
D[0] = 0
def bf(D):
  for i in range(N):
    _D = [d for d in D]
    for s in range(N):
      for adj in E[s]:
        _D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
    D = _D
  return D
D = bf(D)
D1 = [d for d in D]
D = bf(D)
for i in range(N):
  if revG[i] and D1[i] != D[i]:
    print('inf')
    break
else:
  print(-D[-1])

Submission status: Accepted

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:
        pn = dj[-1]
        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
        return inf if pn != dj[-1] else -dj[-1]
    return -dj[-1]

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

print(bf(links, N, 1))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, -c])
D = [N * 10 ** 9 + 1] * N
D[0] = 0
def bf(D):
  for i in range(N):
    _D = [d for d in D]
    for s in range(N):
      for adj in E[s]:
        _D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
    D = _D
  return D
D = bf(D)
d1 = D[-1]
D = bf(D)
print(-d1 if d1 == D[-1] else 'inf')

Submission status: Accepted

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*dist[N]


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: Accepted

Solution code:
INF = float('inf')
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [INF]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

    if negative[-1] is True:
        break
# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)

Submission status: Accepted

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: Accepted

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: Accepted

Solution code:
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), -long(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import heapq

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b, c] =  [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        if a not in graph:
            graph[a] = [(b, -long(c))]
        else:
            graph[a].append((b, -long(c)))

    dummy_inf = long(sys.maxint) * long(sys.maxint)
    dist_list =[dummy_inf for i in range(N + 1)]
    dist_list[1] = 0L

    for i in range(0, 2 * N):
        for j in range(1, N + 1):
            if j not in graph:
                continue
            for edge in graph[j]:
                if dist_list[j] < dummy_inf:
                    new_cost = dist_list[j] + edge[1]
                    if new_cost < dist_list[edge[0]]:
                        dist_list[edge[0]] = new_cost
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()