Meet In The Maze (SRM515 div1 1000)

問題

ルセット、きつね、うさぎ用の入り口がある迷路が与えられる。彼女らは自分専用の入口からランダムに一つ選び迷路の中へ入る。中に入った後に3人の移動距離の合計が最小になるように落ち合う場所を決めその場所へ行く。移動距離の合計の期待値を求めよ。
迷路の大きさ<=(50, 50)
きつね、うさぎ用の入り口<=20

解法

きつね、うさぎの入り口をfixして考える。全セルに関して二人の最短の移動距離の合計を計算する。次に一本鎖のグラフを作り一本鎖のグラフと迷路の間にエッジを作る。エッジは二人の移動距離の合計と一本鎖のグラフのdepth+1が同じになるような場所に張る。このグラフで一本鎖のグラフのdepth 0からルセット用の入り口までの距離が3点の距離の合計になる。
とeditorialに書いてあった。
一本鎖のグラフではきつね、うさぎに歩かせ、迷路の方に入ってからはルセットに歩かせている。