Problem p02949 (python)

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

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000)

from collections import deque

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


visited = [0] * n
def dfs(v):
    for u in edge[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)
visited[0] = 1
dfs(0)
# print(visited)
flag = [vi for vi in visited]

def dfs2(v):
    for u in edge[v]:
        if u == n - 1:
            visited2[u] = 1
            break
        if visited2[u] == 0:
            visited2[u] = 1
            dfs2(u)

for i in range(1, n):
    if flag[i] == 0:
        continue
    visited2 = [0] * n
    visited2[i] = 1
    dfs2(i)
    if visited2[n-1] == 0 and flag[i] == 1:
        flag[i] = 0

# print(flag)
target_v = set([i for i in range(n) if flag[i] == 1])
# print(target_v)

q = deque()
visited3 = [0] * n
visited3[0] = 1
q.append((0, 0, visited3))
ans = [0] * n
iter = 0
impossible = False
while q:
    v, c, visited3 = q.popleft()
    for u in edge[v]:
        if u not in target_v:
            continue
        if visited3[u] == 0:
            ans[u] = c + coin[v][u]
            visited3[u] = 1
            q.append((u, c + coin[v][u]))
        else:
            if ans[u] <= c + coin[v][u]:
                impossible = True
                break

    if impossible:
        break

if impossible:
    print(-1)
else:
    print(max(0, ans[n-1]))

Buggy submission (verdict: Runtime Error):
from collections import deque

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


visited = [0] * n
def dfs(v):
    for u in edge[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)
visited[0] = 1
dfs(0)
# print(visited)
flag = [vi for vi in visited]

def dfs2(v):
    for u in edge[v]:
        if u == n - 1:
            visited2[u] = 1
            break
        if visited2[u] == 0:
            visited2[u] = 1
            dfs2(u)
for i in range(1, n):
    visited2 = [0] * n
    visited2[i] = 1
    dfs2(i)
    if visited2[n-1] == 0 and flag[i] == 1:
        flag[i] = 0

# print(flag)
target_v = set([i for i in range(n) if flag[i] == 1])
# print(target_v)

q = deque()
q.append((0, 0))
visited3 = [0] * n
visited3[0] = 1
ans = [0] * n
iter = 0
impossible = False
while q:
    v, c = q.popleft()
    for u in edge[v]:
        if u not in target_v:
            continue
        if visited3[u] == 0:
            ans[u] = c + coin[v][u]
            visited3[u] = 1
            q.append((u, c + coin[v][u]))
        else:
            if ans[u] <= c + coin[v][u]:
                impossible = True
                break

    if impossible:
        break

if impossible:
    print(-1)
else:
    print(max(0, ans[n-1]))