公式解説の別解 \(2\) は \(O(N + M)\) を達成可能です。

距離は単調増加に処理しなければいけませんが、時間に関しては単調増加に処理する必要性はありません。よって、ふつうのBFSで可能です。

実装例 (PyPy3)

from collections import deque

inf = 1 << 60
n, m, q = map(int, input().split())

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

t = [inf] * m
for i in range(q):
    t[int(input()) - 1] = i

dis = [inf] * n
ans = [0] * n

que = deque([0])
dis[0] = 0
while que:
    u = que.popleft()
    for v, i in e[u]:
        if dis[v] == dis[u] + 1:
            ans[v] = max(ans[v], min(ans[u], t[i]))
        elif dis[v] == inf:
            dis[v] = dis[u] + 1
            ans[v] = min(ans[u], t[i])
            que.append(v)

cnt = [0] * q
for x in ans:
    if x != inf:
        cnt[x] += 1

c = 0
for i in range(q):
    c += cnt[i]
    print(c)