Joeの精進記録

旧:競プロ練習記録

J - Prime Routing

JAG Camp 2018 Day 3の問題

J - Prime Routing

問題の本質を抽出すると次のようになります。

問題

連結で単純な無向グラフが与えられる。頂点Sから頂点Tに向かう奇数長の最短路の長さはいくらか(辺の長さはすべて1)。存在しない場合は-1を出力せよ。

こんなことを考えてハマってしまいました

  • もともと最短路が奇数長ならそれでおk
  • 最短路が偶数長だったら、ちょっと遠回りして奇数長にしなきゃいけない
  • 二部グラフだったらどう頑張っても偶数長。そうでなければ可能
  • 二部グラフじゃないとして、どうやって最短の奇数長を得るか?
  • 二部グラフじゃないなら奇数長のサイクルを含むので、それを見つける?見つけたところで最短の奇数長路をさがすのは難しそう?

解答

各頂点 v v_0, v_1の2つに増やした、頂点数が2倍のグラフを考えます。このとき、元のグラフで a, b間に辺があるとき、 新しいグラフで a_0, b_1間および a_1, b_0間に辺を張ります。このとき、スタートを s, ゴールを tとして  s_0, t_1間の最短距離がスタートからゴールまでの最短の奇数長の路になります。

頂点 aについて、 a_0がスタートから偶数長でたどり着ける頂点、 a_1がスタートから奇数長でたどり着ける頂点だと考えると 納得できると思います。

一般化

今回の問題では奇数長か偶数長かに注目すればいいですが、一般に kの倍数長の最短路を考えるならば、頂点の数を k倍に増やしたような グラフを考えればいいことがわかります。元のグラフの辺 (a, b)に対応して、新しいグラフで k本の辺 (a_0, b_{k - 1}), \ldots, (a_i, a_{(i + 1) \% k}), \ldotsを張ってあげればいいですね。