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: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
from collections import defaultdict,deque
branch=defaultdict(dict)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
check=deque([({0:0},[0])])
inf=10**15
ans=-inf
while len(check)>0:
    scores,visited=check.popleft()
    now=visited[-1]
    for nex,s in branch[now].items():
        if nex==N-1:
            ans=max(ans,scores[now]+s)
        if nex not in visited:
            scores[nex]=scores[now]+s
            check.append((scores,visited+[nex]))
        elif scores[now]>=inf:
            continue
        elif scores[now]+s>scores[nex]:
            scores[nex]=inf
            check.append((scores,[nex]))
if ans>=inf:
    print('inf')
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
graph = [float("INF") for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(2*n):
  flag = False
  for e in edge:
    a, b, c = e
    a, b, c = a-1, b-1, -c
    if graph[b] > graph[a]+c:
      if b==n-1:
        flag = True
      graph[b] = graph[a]+c
if flag:
  print("inf")
else:
  print(-graph[n-1])

Submission status: Time Limit Exceeded

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

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

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

ans = -d[N-1]

negative = [False]*N
for _ in range(N):
	for i in range(M):
		if d[a[i]-1]==INF:
			continue
		if d[b[i]-1]>d[a[i]-1]+c[i]:
			d[b[i]-1] = d[a[i]-1] + c[i]
			negative[b[i]-1] = True
		if negative[a[i]-1]==True:
			negative[b[i]-1] = True

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

Submission status: Time Limit Exceeded

Solution code:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        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):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf')] * self.N
        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):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [-float('inf')] * self.N
        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:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Time Limit Exceeded

Solution code:
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):
        """
        0-indexedでないことに注意
        :param 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):
        # 負の閉路の検出, 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:
                        return True
        return False


N, M = map(int, input().split())
graph = BellmanFord()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

if graph.BellmanFord_negative_bool(N-1):
    print('inf')
else:
    print(-1 * graph.BellmanFord_search(0)[N-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())

a = [0] * m
b = [0] * m
c = [0] * m

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

INF = 10 ** 12

dist = [INF] * n

dist[0] = 0

for j in range(0,n-1):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        dist[b[i]] = min(dist[b[i]], dist[a[i]] + c[i])

ans = - dist[n-1]

negative = [False] * n

for j in range(0,n):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        if dist[a[i]] + c[i] < dist[b[i]]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        elif negative[a[i]]:
            negative[b[i]] = True

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())

a = [0] * m
b = [0] * m
c = [0] * m

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

INF = 10 ** 13

dist = [INF] * n

dist[0] = 0

for j in range(0,n-1):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        dist[b[i]] = min(dist[b[i]], dist[a[i]] + c[i])

ans = - dist[n-1]

negative = [False] * n

for j in range(0,n):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        if dist[a[i]] + c[i] < dist[b[i]]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]]:
            negative[b[i]] = True

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

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

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

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

print(allcost[N])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
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=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while True:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break
else:
    print(-d[n-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
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=99999999999999999999
d=[inf for i in range(n)]
d[0]=0
count=0
while True:
    count+=1
    if count==n:
        tmp=d[n-1]
    update=False
    for i in range(m):
        f,t,cost=edge[i]
        if(d[t]>d[f]+cost):
            d[t]=d[f]+cost
            update=True
    if count==n and tmp!=d[n-1]:
        print('inf')
        break
    if not update:
        print(-d[n-1])
        break

Submission status: Time Limit Exceeded

Solution code:
import sys


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


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

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


inf = 10**15

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

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

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

Submission status: Time Limit Exceeded

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

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


inf = 10**15

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

    if not update:
        break

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())
	A[i] -= 1
	B[i] -= 1
inf = 123456789123456789123456789
dist = [ -inf ] * N
dist[0] = 0
bounded = True
for i in range(2 * N):
	for j in range(M):
		if dist[B[j]] < dist[A[j]] + C[j]:
			dist[B[j]] = dist[A[j]] + C[j]
			if B[j] == N - 1 and i >= N:
				bounded = False
if not bounded:
	print("inf")
else:
	print(dist[N - 1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])
#edges = d
#num_v = n
#source = m


#ベルマンフォード
#高々|V|-1回で最安定経路にたどり着くっていうのがなかなか理解できなくて、紙に書きながら理解した。

"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

"""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(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 1:
            d[n - 1] = -inf
            break
    return d"""
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != 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

print(-shortest_path(edge,n,0)[n - 1])

#print(BellmanFord(e, n, m))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
inf = 10**15
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                if d[b]<d[a]+c:
                    d[b] = d[a]+c
                    update = True
            else:
                update = True
                d[b] = d[a] + c
    if not update:
        break

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                update = True
                updated[b] = True
        if updated[a]:
            update = True
            updated[b] = True
    if not update:
        break

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
inf = 10**15
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                updated[b] = True
        if updated[a]:
            updated[b] = True

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

Submission status: Time Limit Exceeded

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

Cost = [float("inf") for i in range(N)]
Cost[0] = 0
for i in range(N-1):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            Cost[j[1]] = Cost[j[0]] + j[2]     
ans = -Cost[N-1]

Cost = [float("inf") for i in range(N)]
V = [False for i in range(N)]
Cost[0] = 0
for i in range(N):
    for j in P:
        if Cost[j[0]] != float("inf") and Cost[j[1]] > Cost[j[0]] + j[2]:
            if Cost[j[1]] != float("inf"):
                V[j[1]] = True
            Cost[j[1]] = Cost[j[0]] + j[2]    
        if V[j[0]] == True:
            V[j[1]] = True

print("inf" if V[N-1] else ans)

Submission status: Time Limit Exceeded

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 and v == n - 1:
                print('inf')
                exit()
    i += 1

print(-dist[-1])

Submission status: Time Limit Exceeded

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)
    i += 1
    if i > n and v == n-1:
        print('inf')
        exit()
print(-dist[-1])

Submission status: Time Limit Exceeded

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):
    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
            negative[b] = True
        if negative[a]:
            negative[b] = True
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)

Submission status: Time Limit Exceeded

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

edge = [[] for _ in range(n)]
cost = {}

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

d = [inf for _ in range(n)]
d[0] = 0
cnt = 0
while cnt<n:
    update = False
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                update = True
    if not update:
        break
    cnt += 1
ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    for fi in range(n):
        for ti in edge[fi]:
            if d[fi]!=inf and d[ti]>d[fi]+cost[(fi,ti)]:
                d[ti] = d[fi]+cost[(fi,ti)]
                negative[ti] = True
            if negative[fi] == True:
                negative[ti] = True
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)

Submission status: Time Limit Exceeded

Solution code:
'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    update = True
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = False
    if update:
        print(- d[V - 1])
        exit()

for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

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

Submission status: Time Limit Exceeded

Solution code:
'''
V, E : Vは頂点数、Eは辺数
nodes : e = [from, to, cost] を要素とする辺のリスト（有向辺）
☆負のループがあっても、それがゴールと非連結な場所にあった場合関係ない。
つまり「0→負のループ→N-1」という経路が存在するときのみ問題になる。
0→負のループ、という経路があるかどうかは0からの距離がfloat('inf')でないことで調べられる
負のループのある点→N-1という経路があるかどうかは、更新の際にnegative[i]から辺が伸びている頂点も更新することで調べられる。
'''
V, E = map(int, input().split())
nodes = []
for _ in range(E):
    e_from, e_to, e_cost = map(int, input().split())
    e_from -= 1
    e_to -= 1 #頂点を0-indexedに
    e_cost *= -1
    nodes.append([e_from, e_to, e_cost])

d = [float('inf')] * V
negative = [False] * V
d[0] = 0
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
for _ in range(V):
    for e in nodes:
        if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            negative[e[1]] = True
        if negative[e[0]]:
            negative[e[1]] = True

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

Submission status: Time Limit Exceeded

Solution code:
INF = 1<<50
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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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 and t == N - 1:
                inf_flg = True 
    
if inf_flg == True :
    print("inf")
else :
    for c in cost :
        if c == INF :
            print("")
    print(cost[N - 1])

Submission status: Time Limit Exceeded

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 =[long(sys.maxint) * long(sys.maxint) 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] < long(sys.maxint) * long(sys.maxint):
                    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: Time Limit Exceeded

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

    dist_list =[long(sys.maxint) * long(sys.maxint) 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] < long(sys.maxint) * long(sys.maxint):
                    if dist_list[j] + edge[1] < dist_list[edge[0]]:
                        dist_list[edge[0]] = dist_list[j] + edge[1]
                        if (i >= N - 1 and edge[0] == N):
                            print "inf"
                            return
    print -dist_list[N]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def bellmanford(xyw, n, start):
    """2次元配列[[x,y,weight]...], n, start(開始位置)を受け取る"""
    inf = float("inf")
    dist = [inf]*(n+1)
    dist[start] = 0

    for _ in range(n-1):
        for x,y,w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
    result = dist[n-1]
    negative = [0]*n
    for _ in range(n):
        for x, y, w in xyw:
            if dist[x] == inf:
                continue
            if dist[y] > dist[x] + w:
                dist[y] = dist[x] + w
                negative[y] = True
            if negative[x]:
                negative[y] = True
    return inf if negative[n-1] else -result


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

print(bellmanford(ABC, N, 0))

Submission status: Time Limit Exceeded

Solution code:
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
        if negative[a]:
            negative[b] = True

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

Submission status: Time Limit Exceeded

Solution code:
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))
point = [None] * N
point[0] = 0
for i in range((N*3)//2):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(N//2):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)

Submission status: Time Limit Exceeded

Solution code:
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))
point = [None] * N
point[0] = 0
for i in range(N*2):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(N):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)