Problem p02949 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**4)

inf = float('inf')

# 計算量O(VE) V:頂点数, E:辺の数
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    # 頂点数Nなら更新は高々N-1回で済む
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    # 負閉路の検出部分
    # N回目で更新があった場合、負閉路を含む
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

def dfs(v, ad):
    visited[v] = True
    for nv in ad[v]:
        if not visited[nv]:
            dfs(nv, ad)

N, M, P = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    C -= P
    C *= -1
    to[A].append(B)
    fr[B].append(A)
    edges.append((A, B, C))

visited = [False] * N

dfs(0, to)
tmp = visited[:]
visited = [False] * N
dfs(N-1, fr)
visited = [a and b for a, b in zip(tmp, visited)]
edges = [(v, nv, w) for v, nv, w in edges if visited[v] and visited[nv]]

flag = bellmanford(0, N-1)
ans = max(-dist[N-1], 0) if flag else -1
print(ans)

Buggy submission (verdict: Runtime Error):
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = False

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(n-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         exists_negative_cycle = True

    # (2)startとgoalのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(n):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))
 
dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)
 
if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)
 
print(ans)
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         is_cycle = False

    # (2)startとgoalのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)

print(ans)

Buggy submission (verdict: Runtime Error):
inf = float('inf')

# 計算量O(VE) V:頂点数, E:辺の数
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    # 頂点数Nなら更新は高々N-1回で済む
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    # 負閉路の検出部分
    # N回目で更新があった場合、負閉路を含む
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

# 頂点vが1を始点にNにたどり着けるならばTrueを返す
def dfs(v):
    visited[v] = True
    res = False
    if v == N-1:
        res = True
        bit[v] = res
        return res
    for nv, w in ad[v]:
        if not visited[nv]:
            res |= dfs(nv)
    bit[v] = res
    return res

N, M, P = map(int,input().split())
ad = [[] for _ in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    ad[A].append((B, C))
    edges.append((A, B, -C+P))

visited = [False] * N
bit = [False] * N
dfs(0)
# 頂点1から頂点Nのパスに含まれない頂点を削除
edges = [(v, nv, w) for v, nv, w in edges if bit[v] and bit[nv]]

flag = bellmanford(0,N-1)
ans = max(-dist[N-1],0) if flag else -1
print(ans)