ABC299 E問題 Nearest Black Vertex

atcoder.jp

頂点[p_i] から黒頂点までの最短距離が であることから、距離 以下の頂点はすべて白頂点であると確定します。
各頂点について調べることで、白と確定する頂点をすべてリストアップします。
そのあとで、未確定の頂点は黒として、各頂点[p_i] から距離 に黒頂点があるかどうか調べることで判定ができます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N,M = readInts()

  edge = [ [] for i = 1:N ]

  for i = 1:M
    u,v = readInts()
    push!(edge[u], v)
    push!(edge[v], u)
  end

  K = readInt()

  p = zeros(Int,K)
  d = zeros(Int,K)

  for i = 1:K
    p[i],d[i] = readInts()
  end

  color = ones(Int,N)      # 1なら黒, 0なら白
  q = zeros(Int,N)         # 幅優先探索のキュー
  db = [ [] for i = 1:K ]  # p[i] から距離 d[i] の頂点リスト

  for i = 1:K
    dist = fill(-1,N)
    q[1] = p[i]
    dist[p[i]] = 0
    head = 1
    tail = 2
    while head < tail
      a = q[head]
      head += 1
      if dist[a] == d[i]
        push!(db[i],a)
      elseif dist[a] < d[i]
        color[a] = 0      # 距離がd[i]未満は白
      elseif dist[a] > d[i]
        break
      end

      for b in edge[a]
        if dist[b] == -1
          dist[b] = dist[a] + 1
          q[tail] = b
          tail += 1
        end
      end
    end
  end

  for i = 1:K
    black = 0
    for b in db[i]
      black += color[b]
    end
    if black == 0
      println("No")
      return
    end
  end

  println("Yes")
  println(join(color))

end  # function solve

# main
solve()