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:
def shortest_path(s) :
    for i in range(N) :
        dist[i] = float("inf")
    dist[s] = 0
    while True :
        update = False
        for i in range(M) :
            u, v, cost = edges[i]
            if dist[u] != float("inf") and dist[v] > dist[u] + cost :
                dist[v] = dist[u] + cost
                update = True
        if not update :
            break

def find_negative_loop() :
    for i in range(N) :
        dist[i] = 0
    for i in range(N) :
        for j in range(M) :
            u, v, cost = edges[j]
            if dist[v] > dist[u] + cost :
                dist[v] = dist[u] + cost
                if i == N-1 :
                    return True
    return False

N,M = map(int,input().split())
edges = []
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])

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

if find_negative_loop() :
    ans = "inf"
else :
    shortest_path(0)
    ans = dist[N-1] * (-1)

print(ans)

Submission status: Wrong Answer

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

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

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

def bellmanford() :
    for i in range(N) :
        for a, b, c in abc :
            if dist[a] != float('inf') and dist[a] + c < dist[b] :
                dist[b] = dist[a] + c
                if i == N-1 :
                    return True
    return False
    
if bellmanford() :
    print('inf')
else :
    print(-dist[N-1])

Submission status: Wrong Answer

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

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

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

flg = False
for i in range(N) :
    for j in range(N) :
        for bc in v[j] :
            b, c = bc
            if dist[b] > dist[j] - c :
                dist[b] = dist[j] - c
                if i == N-1 :
                    flg = True
                    break
        if flg :
            break

if flg :
    print('inf')
else :
    print(-dist[N-1])

Submission status: Wrong Answer

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

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

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

flg = False
for i in range(N-1) :
    for j in range(N) :
        for bc in v[j] :
            b, c = bc
            if dist[b] > dist[j] - c :
                dist[b] = dist[j] - c
                if i == N-2 :
                    flg = True
                    break
        if flg :
            break

if flg :
    print('inf')
else :
    print(-dist[N-1])

Submission status: Wrong Answer

Solution code:

n, m = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1



for i in range(n-1):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_1 = [ i for i in distance_list]

for i in range(n):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_2 = distance_list



if distance_list_1 == distance_list_2:
    print(-distance_list_1[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1



for i in range(n-1):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_1 = [ i for i in distance_list]

for i in range(n):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_2 = distance_list

check_list = [ distance_list_1[i] == distance_list_2[i] for i in range(n) ]

if all(check_list):
    print(-distance_list_1[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:

n, m = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1


turn = 0
for i in range(n):
    turn += 1 
    change_log = 0
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
    if change_log == 0:
        break

    
def parent(a):
    for i in range(n-1):
        if a == parent_list[a] or a == -1:
            break
        else:
            b = parent_list[a]
            a = b
    return a


if turn != n:
    print(-distance_list[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1


turn = 0
for i in range(n):
    turn += 1 
    change_log = 0
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
    print(distance_list)
    if change_log == 0:
        break

    
def parent(a):
    for i in range(n-1):
        if a == parent_list[a] or a == -1:
            break
        else:
            b = parent_list[a]
            a = b
    return a


if turn != n:
    print(-distance_list[-1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N
negative = [False] * N
#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while count < N -1:
        count += 1
        # print ('A')
        # update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                # update = True
                prev[e[1]] = e[0]
        # if not update:
        #     return True

    count = 0
    while count < N:
        count += 1
        # print ('A')
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] == INF:
                continue
            if d[e[0]] != 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[1]]:
                negative[e[0]] = True


#呼び出しスタート地点を入れる
shortest_path(1)
if not negative[N - 1]:
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Submission status: Wrong Answer

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N
negative = [False] * N
ans = 0
#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while count < N -1:
        count += 1
        # print ('A')
        # update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                # update = True
                prev[e[1]] = e[0]
        # if not update:
        #     return True
    ans = -d[N - 1]

    count = 0
    while count < N:
        count += 1
        # print ('A')
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != 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[1]]:
                negative[e[0]] = True


#呼び出しスタート地点を入れる
shortest_path(1)
if not negative[N - 1]:
    print (ans)
else:
    print ('inf')

# print (d)

Submission status: Wrong Answer

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ


#メイン文
d = [INF] * N #最短距離を記録しておくリスト
prev = [-1] * N
negative = [False] * N

#最短経路復元
def restore(g): #gまでの最短経路を復元
    path = []
    g -= 1 #0-indexに直す
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        # print ('C')
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while count < N -1:
        count += 1
        # print ('A')
        # update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                # update = True
                prev[e[1]] = e[0]
        # if not update:
        #     return True
    
    count = 0
    while count < N:
        count += 1
        # print ('A')
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != 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[1]]:
                negative[e[0]] = True


#呼び出しスタート地点を入れる
shortest_path(1)
if not negative[N - 1]:
    print (-d[N - 1])
else:
    print ('inf')

# print (d)

Submission status: Wrong Answer

Solution code:
#単一始点最短経路問題
#負の閉路があるかどうかの検出
#計算量O(N * M)

INF = 10 ** 15
#入力
N, M = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -s]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [INF] * N #距離を記録
d[0] = 0
def find_negative_loop(): #負の閉路が存在するかを確認
    for i in range(N):
        for j in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                #頂点の回数と同じだけループを回しても更新が起きる-->負の閉回路が存在
                if i == N-1:
                    return True #Trueの時, 負の閉路が存在
    return False #Falseの時, 負の閉路が存在しない

#呼び出しスタート地点を入れる
if find_negative_loop():
    print ('inf')
else:
    print (-d[N - 1])

# print (d)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

n, m = map(int, input().split())

e = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s -= 1
    t -= 1
    c *= -1
    e.append((s, t, c))

dist = [inf] * n
dist[0] = 0
cnt = 0
is_inf = False
while True:
    update = False
    for s, t, c in e:
        if dist[s] != inf and dist[t] > dist[s] + c:
            dist[t] = dist[s] + c
            update = True
    if not update:
        break
    cnt += 1
    # print(*dist)
    if cnt > n:
        is_inf = True
        break

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
link = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    link[a-1].append([b-1, c])
visited = [0] * N
ans = 0

#全ての頂点からループしてないか確かめるといけないかな？
def dfs(v, cnt):
    global ans
    if v == N-1:
        if visited[v] == 0:
            ans = cnt
        else:
            ans = max(ans, cnt)
        for p in link[v]:
            if visited[p[0]] and ans > 0:
                ans = 'inf'
                print(ans)
                exit()
            elif visited[p[0]] and ans <= 0:
                break
    visited[v] = 1
    for nv in link[v]:
        dfs(nv[0], cnt+nv[1])
    return

dfs(0, 0)
print(ans)

Submission status: Wrong Answer

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())
    c[i] = -c[i]
    
INF = 10 ** 10
dist = [INF] * N

dist[0] = 0

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

ans = dist[N-1]

nega = [0] * N

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

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
E=[]
for i in range(m):
    a,b,c=map(int,input().split())
    E.append((a-1,b-1,c))
INF=-10**20
score=[INF]*n
score[0]=0
for i in range(n):
    change=False
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]<score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
                change=True
if change:
    print('inf')
else:
    print(score[n-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
E=[]
for i in range(m):
    a,b,c=map(int,input().split())
    E.append((a-1,b-1,-c))
INF=10**20
score=[INF]*n
score[0]=0
for i in range(n):
    change=False
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]>score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
                change=True
if change:
    print('inf')
else:
    print(-score[n-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
E=[]
for i in range(m):
    a,b,c=map(int,input().split())
    E.append((a-1,b-1,-c))
INF=10**15
score=[INF]*n
score[0]=0
for i in range(n):
    change=False
    for j in range(m):
        e=E[j]
        if score[e[0]]!=INF:
            if score[e[1]]>score[e[0]]+e[2]:
                score[e[1]]=score[e[0]]+e[2]
                change=True
if change:
    print('inf')
else:
    print(-score[n-1])

Submission status: Wrong Answer

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])
  
if len(loop)==0:
  print(d[n-1])
else:
  print("inf")

Submission status: Wrong Answer

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()]]
l=[]
flag=0
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:
                flag=1
                break
            d[i]=d[item]+dist
            q.append([i,dc(s)])
    if flag==1:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Wrong Answer

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]

d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
flag=0
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:
                flag=1
                break
            d[i]=d[item]+dist
            q.append([i,depth+1])
    if flag==1:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Wrong Answer

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]

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

Submission status: Wrong Answer

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]

d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
flag=0
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 i in s:
            if d[i]<d[item]+dist:
                flag=1
            continue
        d[i]=max(d[i],d[item]+dist)
        q.append([i,depth+1])
    if flag==1:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Wrong Answer

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]

d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
flag=0
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 i in s:
            if d[i]<d[item]+dist:
                flag=1
            break
        d[i]=max(d[i],d[item]+dist)
        q.append([i,depth+1])
    if flag==1:
        print("inf")
        break
else:
    print(d[n-1])

Submission status: Wrong Answer

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]

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)
    if item in s:
        print("inf")
        break
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        d[i]=max(d[i],d[item]+dist)
        q.append([i,depth+1])
else:
    print(d[n-1])

Submission status: Wrong Answer

Solution code:
def connect_dfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

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

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

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = c
    v = connect_dfs(N,E,0) & connect_dfs(N,Eb,N-1)
    for i in range(N):
        if i in v:continue
        for j in Eb[i]:
            E[j].pop(i)
    
    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0
    
    for _ in range(N-1):
        d = update(d,N,E,0)
    if d!=update(d,N,E,0):
        print("inf")
    else:
        print(-d[-1])

main()

Submission status: Wrong Answer

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!=d:
    print("inf")
else:
    print(-d[-1])

Submission status: Wrong Answer

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[:]
update()
if dc!=d[:]:
    print("inf")
else:
    print(-d[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# from collections import defaultdict
def main():
    N, M = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = 10**14
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for e in d:
        s, t = e
        if V[s] + d[e] < V[t]:
            V[t] = V[s] + d[e]
    if ans == V[N-1]:
        print(-ans)
    else:
        print("inf")
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# from collections import defaultdict
def main():
    N, M = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = 10**14
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    for e in d:
        s, t = e
        if V[s] + d[e] < V[t] and V[t] == N-1:
            print("inf")
            return
    print(-V[N-1])
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# from collections import defaultdict
def main():
    N, M = map( int, input().split())
    d = dict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = 10**14
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    for e in d:
        s, t = e
        if V[s] + d[e] < V[t]:
            print("inf")
            return
    print(-V[N-1])
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
def main():
    N, M = map( int, input().split())
    d = defaultdict()
    for _ in range(M):
        a, b, c = map( int, input().split())
        a, b = a-1, b-1
        d[(a,b)] = -c
    INF = pow(10,13)
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    for e in d:
        s, t = e
        if V[s] + d[e] < V[t]:
            print("inf")
            return
    print(-V[N-1])
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    q = [] + g[0]
    ans = -10 ** 9 * 1000
    passed = [0]
    while len(q):
        i, k = q.pop(0)
        for b, c in g[i]:
            if b in passed:
                print('inf')
                return
            passed.append(b)
            if b == N - 1:
                ans = max(ans, k + c)
                continue
            q.append((b, k + c))
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import collections

n, m = map(int, input().split())

d = collections.defaultdict(dict)
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = c

def f():
    stack = [(1, 0, set())]
    ans = -float('inf')
    while stack:
        a, x, s = stack.pop()

        if len(d[a]) == 0:
            ans = max(ans, x)

        for b, c in d[a].items():
            if b in s:
                return 'inf'
            
            t = set(s)
            t.add(a)
            stack.append((b, x + d[a][b], t))
    
    return ans


print(f())

Submission status: Wrong Answer

Solution code:
N,M = [int(s) for s in input().split()]
dist = [-10**9]*N
E = []
flag = 0
change = 0
N_flag = 0
for i in range(M):
    a,b,c = [int(s) for s in input().split()]
    E.append((a,b,c))
dist[0] = 0
for i in range(N):
    for (a,b,c) in E:
        if a == N or b == N:
            N_flag = 1
        newLen = dist[a-1] + c
        if newLen > dist[b-1]:
            change = 1
            dist[b-1] = newLen
            if i == N-1 and change == 1 and N_flag == 1:
                flag = 1
        change = 0
        N_flag = 0
if flag == 1:
    print('inf')
else:
    print(dist[N-1])