ABC299E - Nearest Black Vertex

考え方

隣接頂点との距離が1なので，BFSで最短距離を求められる．
最短経路問題 - 競プロはじめました

各$p_{i}$からの各頂点の最短距離$d$を求めて，$d < d_{i}$となる頂点は白に塗らなければならない．この集合をwhiteとする．

各$i$について$p_{i}$からの最短距離が$d_{i}$に等しい頂点の集合をbとする．bがwhiteに包含されていれば答えはNoとなる．
そうでなければ，bの要素でwhiteに含まれないものを黒に塗れば良い．

回答例

from collections import deque

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

K = int(input())
PD = [list(map(int, input().split())) for _ in range(K)]
black = []
white = set()
for p, d in PD:
    p -= 1
    q = deque([(p, 0)])
    seen = [False] * N
    b_loc = set()
    while q:
        cur, dist = q.popleft()
        seen[cur] = True
        if dist == d:
            b_loc.add(cur)
        elif dist < d:
            white.add(cur)
        elif dist > d:
            break
        for chi in G[cur]:
            if seen[chi]:continue
            q.append((chi, dist + 1))
    black.append(b_loc)

for b in black:
    diff = b - white
    if not diff:
        exit(print('No'))

ans = ['1'] * N
for w in white:
    ans[w] = '0'

print('Yes')
print(''.join(ans))