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:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
G = [[-float('inf')] * N for _ in range(N)]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N

for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c

updated = [False] * N
updated[0] = True
updated2 = False
for n in range(N):
    for i in range(1, N+1):
        if not updated[i-1]:
            continue
        updated[i-1] = False
        for j in range(1, N+1):
            # print('i={}, j={}'.format(i, j), end='')
            if i == j:
                # print(score)
                continue
            if G[i-1][j-1] != -float('inf') and score[j-1] < score[i-1] + G[i-1][j-1]:
                score[j-1] = score[i-1] + G[i-1][j-1]
                updated[j-1] = True
                if j == N-1:
                    updated2 = True
            else:
                if j == N-1:
                    updated2 = False
            # print(score)

if updated2:
    print('inf')
else:
    print(score[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
G = [[-float('inf')] * N for _ in range(N)]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N

for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c

updated = True
updated2 = False
for n in range(N):
    updated = False
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i == j:
                continue
            if G[i-1][j-1] != -float('inf') and score[j-1] < score[i-1] + G[i-1][j-1]:
                score[j-1] = score[i-1] + G[i-1][j-1]
                updated = True
                if j == N-1:
                    updated2 = True
            else:
                if j == N-1:
                    updated2 = False

if updated2:
    print('inf')
else:
    print(score[N-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

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

for j in range(N):
    for i in range(M):
        if d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]

for i in range(N):
    for j in range(M):
        if d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True

        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

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

Submission status: Time Limit Exceeded

Solution code:
def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0

    changed = True

    while changed:
        count  += 1
        if count == 500000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist


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

res = bell(edges, n)

print(res[n-1])

Submission status: Time Limit Exceeded

Solution code:
def bell(edges, n):
    count = 0
    dist = [-10000000000000000 for i in range(n)]
    dist[0] = 0

    changed = True

    while changed:
        count  += 1
        if count == 1000000:
            print('inf')
            exit()
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                changed = True
            dist[edge[1]] = max(dist[edge[0]] + edge[2], dist[edge[1]])
                
    return dist


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

res = bell(edges, n)

print(res[n-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
queue = [0]
nque = []
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []

while queue:
    q = queue.pop(-1)
    for a,c in side[q]:
        if node[a] < node[q]+c:
            node[a] = float('inf')
            queue.append(a)

print(node[-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
queue = [0]
nque = []
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []
ans = node[-1]
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []
if node[-1] == ans:
    print(ans)
else:
    print('inf')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        memo[u]=s
        for v,c in ot[u]:
            if route[v]:
                if s+c>memo[v]:
                    return True
                continue
            if dfs(v,s+c):return True
            score[u]=max(score[u],score[v]+c)
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    memo = [0] * n
    score[0]=0
    route=[False]*n
    if dfs(n-1):
        print("inf")
    else:
        print(score[n-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        score[u]=s
        res=-inf
        if u==0:res=0
        for v,c in ot[u]:
            if route[v]:
                if s+c>score[v]:
                    return inf
                continue
            ret=dfs(v,s+c)
            if ret==inf:return inf
            res=max(res,ret+c)
        route[u]=False
        return res

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    score[0]=0
    route=[False]*n
    ans=dfs(n-1)
    if ans==inf:
        print("inf")
    else:
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
"""
検討
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計
"""

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

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for edge in edges:
        if dist[edge[0]] == inf:
            continue
        if dist[edge[1]] > dist[edge[0]] + edge[2]:
            dist[edge[1]] = dist[edge[0]] + edge[2]
ans = -dist[n-1]

negative = [False for _ in range(n)]
for i in range(n):
    for edge in edges:
        if dist[edge[0]] == inf:
            continue
        if dist[edge[1]] > dist[edge[0]] + edge[2]:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            negative[edge[1]] = True
        if negative[edge[0]]:
            negative[edge[1]] = True

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

Submission status: Time Limit Exceeded

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

def bellman_ford(n, E, s=0):
    D = [1<<100] * n
    D[s] = 0
    f = 1
    k = 0
    while f:
        f = 0
        for i in range(n):
            for j, c in E[i]:
                if D[i] < 1<<100 and D[j] > D[i] + c:
                    D[j] = D[i] + c
                    f = 1
                    if k == N-1 and j == N-1: return (1, [])
        k += 1
    return (0, D)

b, d = bellman_ford(N, E1)
if b:
    print("inf")
else:
    print(-d[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = set()
while cur != 0:
    root.add(cur)
    cur = before_ls[cur]
root.add(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = []
while cur != 0:
    root.append(cur)
    cur = before_ls[cur]
root.append(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance.copy()
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            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 or loop_cnt > n: break
    return d, (loop_cnt > n)

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

dist, cycle = bellman_ford(n, edges, 0)
if not cycle:
    print(-dist[n-1])
else:
    test, _ = bellman_ford(n, edges, 0, dist)
    if dist[n-1] != test[n-1]:
        print("inf")
    else :
        print(-dist[n-1])

Submission status: Time Limit Exceeded

Solution code:
def bellman_ford(n, edges, s, distance=None):
    if distance != None:
        d = distance.copy()
    else :
        d = [float('inf')] * n
        d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            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 or loop_cnt > n: break
    return d

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

dist = bellman_ford(n, edges, 0)
test = bellman_ford(n, edges, 0, dist)

if dist[n-1] > test[n-1]:
    print("inf")
else :
    print(-dist[n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in abc:
    a,b,c=u
    data[a].append([b,c])
inf=float("inf")
lst=[-inf]*(n+1)
lst[1]=0
que=[1]
count=0
z=0
a,b,c,d=-inf,-inf,-inf,-inf
while que:
    h=[]
    for u in que:
        for v in data[u]:
            w,c=v
            lst[w]=max(lst[w],lst[u]+c)
            h.append(w)
    que=h
    count+=1
    if count==m:
        a=lst[n]
    if count==2*m+5:
        b=lst[n]
        break
    if len(que)>n:
        c=lst[n]
        z=10
    if z>=10:
        z+=1
        if z==15:
            d=lst[n]
            break
else:
    print(lst[n])
    sys.exit()
if b>a or d>c:
    print("inf")
else:
    print(lst[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in abc:
    a,b,c=u
    data[a].append([b,c])
inf=float("inf")
lst=[-inf]*(n+1)
lst[1]=0
que=[1]
count=0
while que:
    h=[]
    for u in que:
        for v in data[u]:
            w,c=v
            lst[w]=max(lst[w],lst[u]+c)
            h.append(w)
    que=h
    count+=1
    if count==m:
        a=lst[n]
    if count==2*m+5:
        b=lst[n]
        break
else:
    print(lst[n])
    sys.exit()
if b>a:
    print("inf")
else:
    print(lst[n])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


N,M = map(int,input().split())

dic = {}

for i in range(M):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []

    dic[a].append([b,c])

lis = [[0] * N for j in range(N)]
lis[0][0] = 1
lmax = [0] * N
lmax[0] = 1

mcost = [-1 * float("inf")] * N
mcost[0] = 0

q = deque([])
q.append(0)

while len(q) > 0:

    now = q.pop()

    if now not in dic or lmax[now] > N:
        continue

    for npath in dic[now]:

        b = npath[0]
        c = npath[1]

        if mcost[now] + c > mcost[b]:
            mcost[b] = mcost[now] + c
            lis[b] = lis[now].copy()
            lmax[b] = lmax[now]
            lis[b][b] += 1
            lmax[b] = max(lmax[b],lis[b][b])
            q.append(b)

    if lis[N-1][N-1] != -1 * float("inf") and lmax[N-1] >= 2:
        mcost[N-1] = float("inf")
        break

print (mcost[N-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
INF = 10**12
edges = [tuple(map(int, input().split())) for _ in range(M)]
dp = [-INF] * (N+1)
cnt = 0
dp[1] = 0
while True:
  update = False
  for a, b, c in edges:
    if dp[a] != -INF and dp[b] < dp[a] + c:
      dp[b] = dp[a] + c
      update = True
      cnt += 1
  if update:
    if cnt == N:
      print('inf')
      exit()
  else:
    break
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())

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

INF = 1e18
distance = [INF] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
            if b == N and count == N:
                print("inf")
                sys.exit()
    if not update:
        break

print(-distance[N - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())

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

INF = 1e18
distance = [INF] * N
distance[0] = 0

count = 0
while True:
    count += 1
    update = False
    for i in range(M):
        a, b, c = graph[i]
        if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
            distance[b - 1] = distance[a - 1] + c
            update = True
    if not update:
        break
    if count == N and b == N:
        print("inf")
        sys.exit()

print(-distance[N - 1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC61 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-inf for _ in range(n)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    cnt = 0
    while 1:
        cnt += 1
        update = False
        for i in range(n):
            for edge in edges:
                e_from, e_to, e_cost = edge
                if e_from != inf and dist[e_to] < dist[e_from] + e_cost:
                    dist[e_to] = dist[e_from] + e_cost
                    update = True
        if not update:
            break
        if cnt == n - 1:
            d = dist[:]
        elif cnt > n - 1:
            if d[-1] < dist[-1]:
                print('inf')
                quit()
                return
            else:
                return d[-1]
    return dist[-1]

n,m = LI()
edges = []
for _ in range(m):
    a,b,c = LI()
    edges.append([a-1,b-1,c])

ans = Bellman_Ford(edges,0)
print(ans)

Submission status: Time Limit Exceeded

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

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

visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]
# print(target_nodes)

def bellman_ford(n, edge):
    INF = float('inf')
    d = [INF] * n
    d[0] = 0
    for i in range(n):
        update = False
        for v_from, v_to, cost in edge:
            if v_from not in target_nodes or v_to not in target_nodes:
                continue
            if d[v_from] != INF and d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost # 緩和
                update = True
    return d, update

d, update = bellman_ford(n, edge)
if update:
    print("inf")
else:
    print(-d[n-1])

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N, M = map(int, input().split())
dist = [0] + [INF] * (N-1)
abc = []

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append((a, b, -c))
    
for i in range(N-1):
    for a, b, c in abc:
        dist[b-1] = min(dist[b-1], dist[a-1]+c)
        
ans = dist[-1]
negative = [False] * N

for i in range(N):
    for a, b, c in abc:
        if dist[b-1] > dist[a-1]+c:
            dist[b-1] = dist[a-1]+c
            negative[b-1] = True
        if negative[a-1]:
            negative[b-1] = True
        
if negative[-1]:
    print('inf')
else:
    print(-ans)

Submission status: Time Limit Exceeded

Solution code:
#D問題
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
    return dist

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

negative = [False for i in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(M):
        if Dist[ABC[j][0]-1] == inf:
            continue
        if Dist[ABC[j][1]-1] > Dist[ABC[j][0]-1]+ABC[j][2]:
            Dist[ABC[j][1]-1] = Dist[ABC[j][0]-1]+ABC[j][2]
            negative[ABC[j][1]-1] = True
            
        if negative[ABC[j][0]-1] == True:
            negative[ABC[j][1]-1] = True


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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
  
c=[False for _ in [0]*n]
for x in loop:
    if c[x]==True:
        continue
    q=[x]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
if c[n-1]==True:
    print("inf")
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
    
for x in loop:
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
    if c[n-1]==True:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
    
def check(x):
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
        if c[n-1]==True:
            return True
    else:
        return False
    
for x in loop:
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
    if c[n-1]==True:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
    
def check(x):
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
    return c[n-1]
  
for i in loop:
    if check(i)==True:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
    
def check(x):
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
        if c[n-1]==True:
            return True
            break
    else:
        return False
    
for i in loop:
    if check(i)==True:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy as dc
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,set()]]
flag=0
loop=set()
while q:
    item,s=q.pop()
    #print(item,s)
    s.add(item)
    #print(g[item])
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                #print(i)
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,dc(s)])
    
def check(x):
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
    return c[n-1]
for i in loop:
    if check(i)==True:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c


INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True

for _ in range(N-1):update()
dc = d[:]
for _ in range(N):update()
if dc[-1]!=d[-1]:
    print("inf")
else:
    print(-d[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
gra = [[]for i in range(N)]
p = [[0]+[-float("inf")]*(N-1) for i in range(N*2+1)]
p[0][0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    gra[a-1].append([b-1,c])
for i in range(N*2):
    for j in range(N):
        for b,c in gra[j]:
            p[i+1][b] = max(p[i+1][b],p[i][j]+c,p[i][b])
print(["inf",p[N][-1]][p[N][-1] == p[-1][-1]])

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
inf=10**15
dist=[(-inf,set())]*N
dist[0]=(0,{0})
check={0}
while len(check)>0:
    now=check.pop()
    for nex,s in branch[now].items():
        if nex not in dist[now][1]:
            dist[nex]=(dist[now][0]+s,dist[now][1]|{nex})
            check|={nex}
        elif dist[now][0]>=inf:
            continue
        elif dist[now][0]+s>dist[nex][0]:
            dist[nex]=(inf,{nex})
            check|={nex}
if dist[N-1][0]>=inf:
    print('inf')
else:
    print(dist[N-1][0])