白準1948号:臨界経路

白準1948号:臨界経路
解法
その前に白準5719号:ほぼ最短経路を解読し,BFSを逆追跡するアイデアを容易に思いついた.
正しいコード

import sys
from collections import deque, defaultdict
input = sys.stdin.readline


N, M = int(input()), int(input())
L, L_reverse = defaultdict(list), defaultdict(list)
C = [0] * (N + 1)
for i in range(M):
    a, b, c = map(int, input().split())
    L[a].append((b, c))
    L_reverse[b].append((a, c))
    C[b] += 1
start, end = map(int, input().split())
    
Q = deque()
Q.append((0, start))

D = [0] * (N + 1)
while Q:
    SD, SN = Q.popleft()

    for FN, FD in L[SN]:
        C[FN] -= 1
        D[FN] = max(D[FN], SD + FD)
        if not C[FN]:
            Q.append((D[FN], FN))

Q = deque()
Q.append(end)

V = defaultdict(int)
V[end] = 1

count = 0
while Q:
    SN = Q.popleft()

    for FN, FD in L_reverse[SN]:
        if FD + D[FN] == D[SN]:
            count += 1
            if not V[FN]:
                Q.append(FN)
                V[FN] = 1

print(D[end])
print(count)

反省点
バックトレースBFS中に頂点にアクセスするかどうかを記録するのは,以降の繰返しカウントを防ぐためである.しかし、アクセスの頂点の幹線を計算しないわけにはいかない.おかげで30分も時間を無駄にしました.