ABC289 E問題 Swap Places

atcoder.jp

二人の位置を一つの状態にしよう

高橋君が頂点 1 から頂点 N に移動し、青木君が頂点 N から頂点 1 に移動するまでのグラフの最短距離を求める問題ですが、
二人が同時に動き、かつ同色の頂点に移動できないという制約条件があります。そのため、二人の動きを独立に考えることはできません。
そこで二人の位置をまとめて、高橋君が頂点 に青木君が頂点 にいる状態を と表すという工夫を行います。
頂点 と 、頂点 と頂点 がそれぞれ辺で結ばれている場合で、頂点の色が異なる場合、
状態 から状態 へ移動することができます。
このことを、とを頂点として、これらが辺で結ばれているグラフとみなします。
そして、このグラフに最短経路を求めるアルゴリズムであるダイクストラ法を適用してみます。

ダイクストラ法

ダイクストラ法では、最短経路を記録する配列と、未確定の頂点の優先度付きキューを利用します。
最短経路を記録する配列は、一次元配列ではなく二次元配列とします。
また、辺の重みはすべて 1 になるため、優先度付きキューの代わりに、キュー(先入れ先出し)として問題ありません。

コード例 (Julia)

function solve_test()

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

  # 入力データ
  N,M = readInts()

  u = zeros(M)
  v = zeros(M)

  # 頂点の色
  C = readInts()

  # グラフの辺
  edge = [Vector{Int}() for _ = 1:N]

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

  if C[1] + C[N] != 1
    # 1 と N の色が同じ場合、高橋君が頂点 N 、青木君が頂点 1 に同時に移動することができない
    println("-1")
    return
  end

  # 高橋君が頂点 i 、青木君が頂点 j の状態までの行動回数 (未到達の場合 -1)
  step = fill(-1, N,N)  # 二次元配列

  step[1,N] = 0    # 高橋君が頂点 1 、青木君が頂点 N がスタート地点

  # ダイクストラ法
  Q = [(1,N)]     # スタート地点をキューに代入してwhileループ開始

  while  !isempty(Q)  # キューが空になるまでループを実行する

    i,j = popfirst!(Q)  # キューの先頭を取り出す

    ni = length(edge[i])
    nj = length(edge[j])
    for p = 1:ni
      for q = 1:nj
        next_i = edge[i][p]
        next_j = edge[j][q]
        if step[next_i,next_j] != -1
          continue   # すでに探索済み
        end

        if  C[next_i] == C[next_j]
          continue   # 同じ色には移動できない
        end

        step[next_i,next_j] = step[i,j] + 1  # 各辺の重みは 1
        push!(Q,(next_i,next_j))    # キューの最後尾に追加
      end
    end
  end

  println(step[N,1]) # 高橋君が頂点 N 、青木君が頂点 1 の状態までのステップ数

end

function solve()

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

  # 入力データ
  T = readInt()

  for t = 1:T
    solve_test()
  end

end  # function solve

# main
solve()