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:
n, m = map(int, raw_input().split())
g = [[] for i in xrange(n)]
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    g[a-1].append((b-1, c))
dist = [-10**18]*n


import sys
sys.setrecursionlimit(10**6)
used = [0]*n
valid = [0]*n
memo = [None]*n
loop = [0]*n
def dfs(v):
    res = 0
    if memo[v] is not None:
        return memo[v]
    for t, c in g[v]:
        if not used[t]:
            if t == n-1:
                res = 1
            used[t] = 1
            res |= dfs(t)
            used[t] = 0
        else:
            loop[t] = 1
    valid[v] |= res
    memo[v] = valid[v]
    return res
valid[0] = valid[n-1] = 1
used[0] = 1
dfs(0)

dist[0] = 0
for t in xrange(2*n):
    update = 0
    for v in xrange(n):
        for t, c in g[v]:
            if valid[t] and dist[v] + c > dist[t]:
                dist[t] = dist[v] + c
                update = 1
if update == 1 or any(loop[v] for v in xrange(n) if valid[v]):
    print "inf"
else:
    print dist[n-1]

Submission status: Wrong Answer

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

class Bellman_Ford(object):
	"""
	ベルマンフォード法, O(EV)
	ステータス:distance(list),prev(list),length(int)
	edge=[i, j, cost] のリスト
	"""
	def __init__(self, edge, start, length):
		self.start=start
		self.length=length
		self.distance=[float("inf") for x in range(self.length)]
		self.distance[start]=0
		self.prev=[0 for x in range(self.length)]
		self.prev[start]=-1
		self.solvable=True
		def update():
			for i in edge:
				d=self.distance[i[0]]+i[2]
				if d<self.distance[i[1]]:
					self.distance[i[1]]=d 
					self.prev[i[1]]=i[0]
		for i in range(length-1):
			update()
		memo=[]
		for i in self.distance:
			memo.append(i)
		update()
		if memo!=self.distance:
			self.solvable=False

	def route(self,goal):
		route=[]
		while(True):
			route.append(self.prev[goal])
			goal=self.prev[goal]
			if goal==self.start:
				break
		route.reverse()
		return(route)

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

B = Bellman_Ford(edges,0,N)
if not B.solvable:
	print("inf")
else:
	print(-B.distance[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, -c))
        
dist = [float('inf') for i in range(n)]
dist[0] = 0
prev = [-1 for i in range(n)]
negative_cycle = False
for k in range(n):
    for i in range(n):
        for dst, cst in g[i]:
            src = i
            if dist[dst] > dist[src] + cst:
                dist[dst] = dist[src] + cst
                prev[dst] = src
                if k == n-1:
                    dist[dst] = -float('inf')
                    negative_cycle = True

if negative_cycle:
    print('inf')
else:
    print(-dist[n-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
g = [[] for i in xrange(n)]
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    g[a-1].append((b-1, c))
dist = [-10**18]*n
dist[0] = 0
for t in xrange(n):
    update = 0
    for v in xrange(n):
        for t, c in g[v]:
            if dist[v] + c > dist[t]:
                dist[t] = dist[v] + c
                update = 1
if update == 1:
    print "inf"
else:
    print dist[n-1]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = float('inf')
N, M = map(int, raw_input().split())
abc = [map(int, raw_input().split()) for i in xrange(M)]
abc = [[a - 1, b - 1, c] for a, b, c in abc]

def find_negative_loop():
    d = [0]*N
    for i in xrange(N):
        for a, b, c in abc:
            if d[b] > d[a] - c:
                d[b] = d[a] - c
                if i == N - 1: return True
    return False

def bellman_ford(s):
    d = [inf]*N
    d[s] = 0
    while True:
        update = False
        for a, b, c in abc:
            if d[a] != inf and d[b] > d[a] - c:
                d[b] = d[a] - c
                update = True
        if not update:
            break
    return d

if find_negative_loop():
    print 'inf'
else:
    d = bellman_ford(0)
    print -d[N - 1]

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()

def bf(es, n, start):
    I = 999999999999999999
    d = [I] * n
    d[start] = 0

    for i in range(n-1):
        updated = False
        for e in es:
            if d[e[0]] == I: continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for e in es:
        if d[e[0]] == I: continue
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

res = bf(es, n, 0)
if res:
    print(-res[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()

def bf(es, n, start):
    d = [999999999999999999] * n
    d[start] = 0
    m = len(es)

    for i in range(2500):
        updated = False
        for j in range(m):
            e = es[j]
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for j in range(m):
        e = es[j]
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

res = bf(es, n, 0)
if res:
    print(-res[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()

def bf(es, n, start):
    d = [999999999999999999] * n
    d[start] = 0
    m = len(es)

    for i in range(4000):
        updated = False
        for j in range(m):
            e = es[j]
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for j in range(m):
        e = es[j]
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

res = bf(es, n, 0)
if res:
    print(-res[n-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()

def bf(es, n, start):
    d = [999999999999999999] * n
    d[start] = 0
    m = len(es)

    for i in range(n-1):
        updated = False
        for j in range(m):
            e = es[j]
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for j in range(m):
        e = es[j]
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

res = bf(es, n, 0)
if res:
    print(-res[n-1])
else:
    print("inf")

Submission status: Time Limit Exceeded

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

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    cnt = 0
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
                if cnt == n-1 and e.end == n-1:
                  print('inf')
                  sys.exit()
        cnt += 1
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))


print(-bellman_ford(N, es,0)[N-1])

Submission status: Time Limit Exceeded

Solution code:

INF = float('inf')
N, M = map(int, input().split())

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n - 1 and e.end == n - 1:
                    return True
    return False

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
else:
  print(-bellman_ford(N, es,0)[N-1])

Submission status: Time Limit Exceeded

Solution code:
class PreallocatedQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.init_val = init_val
        self.count = 0

    def append(self, val):
        if self.count == self.n:
            if self.r == 0:
                self.queue = self.queue + [self.init_val] * self.n
            else:
                self.queue = self.queue[self.l:] + self.queue[:self.r] + [self.init_val] * self.n
                self.l = 0
            self.r = self.n
            self.n *= 2
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.count += 1

    def popleft(self):
        if self.count == 0:
            raise IndexError('popleft from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.count -= 1
        return val

    def pop(self):
        if self.count == 0:
            raise IndexError('pop from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.count -= 1
        return val
    
    def size(self):
        return self.count
    
    def __bool__(self):
        return self.count != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = PreallocatedQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.count
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def moores_d(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    for _ in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = minus_inf
                    q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = moores_d(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
sc=0
for _ in range(m):
  a,b,c=map(int,input().split())
  e[a]+=[(b,c)]
  sc+=max(c,0)
q=[1]
vis=[-10**18]*(n+1)
vis[1]=0
while q:
  now=q.pop()
  for to,cost in e[now]:
    q+=[to]
    vis[to]=max(vis[now]+cost,vis[to])
  if vis[n]>sc:
    print('inf')
    exit()
print(vis[n])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

G = nx.DiGraph()

N, M = map(int, input().split())
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, weight=-c)

rev = G.reverse(copy=False)
c = nx.unweighted.single_source_shortest_path(rev, N).keys()
sG = G.subgraph(c)

try:
    print(-nx.bellman_ford_path_length(sG, 1, N))
except nx.NetworkXUnbounded:
    print('inf')

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
edges = [[] for i in range(N)]
for i in range(M):
    a, b, c = getNM()
    edges[a - 1].append([b - 1, c])

pos = deque([[1, 0, 0]])
point = [-float('inf')] * N
route = [0] * N

while len(pos) > 0:
    s, u, dis = pos.popleft()
    if s == route[u]:
        if u == N - 1 and dis > point[u]:
            print('inf')
            exit()
        continue
    point[u] = max(point[u], dis)
    route[u] = s
    for i in edges[u]:
        new = s | (1 << i[0])
        pos.append([new, i[0], dis + i[1]])
        
print(point[N - 1])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

G = nx.DiGraph()

N, M = map(int, input().split())
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, weight=-c)

cG = G.copy()
cG.add_edge(N, 1)
for c in nx.strongly_connected_components(cG):
    if 1 in c:
        sG = G.subgraph(c)
        break
try:
    print(-nx.bellman_ford_path_length(sG, 1, N))
except nx.NetworkXUnbounded:
    print('inf')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:
    def __init__(self, fr, to, cost):
        self.fr, self.to, self.cost = fr, to, cost

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    es = []
    for _ in range(M):
        a, b, c = ZZ()
        a -= 1
        b -= 1
        es.append(edge(a, b, -c))

    #負の閉路検出
    d = [0] * N
    for i in range(N):
        for e in es:
            if d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                if e.to == N-1 and i == N-1:
                    print('inf')
                    return
    #ベルマンフォードする
    d = [INF] * N
    d[0] = 0
    while True:
        update = False
        for e in es:
            if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
                d[e.to] = d[e.fr] + e.cost
                update = True
        if not update: break
    print(-d[N-1])

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  #無向グラフの場合
            self.e[u].append((v,d))
            self.e[v].append((u,d))
        else:  #有向グラフの場合
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  #sから各点までの最短距離
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        if i == self.N - 1:
                            return True
        return False

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

print(-G.BellmanFord_search(1)[N])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
edge = [[] for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a].append((b,-c))


from heapq import *
def dijkstra(s,g):
    INF = float("inf")
    d = [INF]*(n+1)
    queue = []
    d[s] = 0
    renew = set()
    heappush(queue,(d[s],s))
    while len(queue) > 0:
        dist,u = heappop(queue)
        for v,cost in edge[u]:
            if dist + cost <= d[v]:
                d[v] = dist + cost
                if (u,v) in renew:
                    d[v] = -INF
                    renew.add((u,v))
                heappush(queue,(d[v],v))
    return d
print(-dijkstra(1,n)[n])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
edge = [[] for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a].append((b,-c))


from heapq import *
def dijkstra(s,g):
    INF = float("inf")
    d = [INF]*(n+1)
    queue = []
    d[s] = 0
    renew = set()
    heappush(queue,(d[s],s))
    while len(queue) > 0:
        dist,u = heappop(queue)
        for v,cost in edge[u]:
            if dist + cost <= d[v]:
                d[v] = dist + cost
                if v in renew:
                    d[v] = -INF
                    renew.add(v)
                heappush(queue,(d[v],v))
    return d
print(-dijkstra(1,n)[n])

Submission status: Time Limit Exceeded

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

def shortest_path(s):
    MIN = -1 * 10 ** 12
    d = [MIN] * (n + 1)
    d[s] = 0
    update = True
    cnt = 1
    tmp = MIN
    while update:
        update = False
        for a, b, c in graph:
            if d[a] != MIN and d[b] < d[a] + c:
                d[b] = d[a] + c
                update = True
        if cnt == m: tmp = d[n]
        if update and cnt == 2 * m and d[n] > tmp: return 'inf'
        cnt += 1
    return d[n]

print(shortest_path(1))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    adjacent.append([a-1, b-1, c])
for i in range(2*N):
    for j in adjacent:
      if score[j[1]] == 'None' and score[j[0]] != 'None':
        score[j[1]] = score[j[0]] + j[2]
      if score[j[1]] != 'None' and score[j[0]] != 'None':
        if score[j[1]] < score[j[0]] + j[2]:
          score[j[1]] = score[j[0]] + j[2]
    if i == N-2:
      t = score[N-1]
    if i == 2*N-1:
      if t != score[N-1]:
        score[N-1] = 1e+15
if score[N-1] < 1e+15:
    print(t)
else:
    print('inf')

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1 and e[1] == numNodes-1:
                        return True
        return False

n,m = na()
g = BellmanFord()

for i in range(m):
    a,b,c = na()
    a,b,c = a-1,b-1,-c
    g.add(a, b, c, directed=True)

if g.BellmanFord_negative_bool(n):
    print('inf')

d = g.BellmanFord_search(0)

print(-d[n-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
array = [tuple(int(x) for x in input().split()) for x in range(M)]
score = [-float("inf") for x in range(N)]
score[0] = 0
check = 0
while(True):
    if(N == 1):
        check = score[-1]
    elif(N < 1):
        if(check == score[-1]):
            pass
        elif(check < score[-1]):
            print("inf")
            break
        elif(check > score[-1]):
            print(check)
            break
    now = score.copy()
    for j in array:
        if(score[j[0]-1] + j[2] > score[j[1]-1]):
            score[j[1]-1] = score[j[0]-1] + j[2]
    if(now == score):
        print(score[-1])
        break
    N += -1

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist

    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and (v == V-1 or u == V-1):return True

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    if bf.findneg(N,E):
        print('inf')
    else:
        ans = bf.bellmanford(0,N,E)
        print(-ans[-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist

    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and v == V-1:return True

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    if bf.findneg(N,E):
        print('inf')
    else:
        ans = bf.bellmanford(0,N,E)
        print(-ans[-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist


def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    ans = dist[-1]
    neg = [False for _ in range(N)]
    for l in range(N):
        for e in E:
            a,b,c = e
            if dist[a] == INF:continue
            if dist[b] > dist[a]+c:
                neg[b] = True
            if neg[a]:
                neg[b] = True
    if neg[-1]:
        print("inf")
    else:
        print(-ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[a] == float("inf"):
				continue

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

Submission status: Time Limit Exceeded

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

dist = [float("inf")] * n


def bellman_ford(s):
	dist[s] = 0

	for i in range(n - 1):
		for j in range(m):
			a, b, c = abc[j]
			a -= 1
			b -= 1
			c = -c

			if dist[a] == float("inf"):
				continue

			dist[b] = min(dist[b], dist[a] + c)


bellman_ford(0)
ans = -dist[-1]

negative = [False] * n

for i in range(n):
	for j in range(m):
		a, b, c = abc[j]
		a -= 1
		b -= 1
		c = -c

		if dist[a] == float("inf"):
			continue

		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			negative[b] = True

		if negative[a]:
			negative[b] = True

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