JAG Camp 2018 Day 3の問題
問題の本質を抽出すると次のようになります。
問題
連結で単純な無向グラフが与えられる。頂点Sから頂点Tに向かう奇数長の最短路の長さはいくらか(辺の長さはすべて1)。存在しない場合は-1を出力せよ。
こんなことを考えてハマってしまいました
- もともと最短路が奇数長ならそれでおk
- 最短路が偶数長だったら、ちょっと遠回りして奇数長にしなきゃいけない
- 二部グラフだったらどう頑張っても偶数長。そうでなければ可能
- 二部グラフじゃないとして、どうやって最短の奇数長を得るか?
- 二部グラフじゃないなら奇数長のサイクルを含むので、それを見つける?見つけたところで最短の奇数長路をさがすのは難しそう?
解答
各頂点をの2つに増やした、頂点数が2倍のグラフを考えます。このとき、元のグラフで間に辺があるとき、 新しいグラフで間および間に辺を張ります。このとき、スタートを, ゴールをとして 間の最短距離がスタートからゴールまでの最短の奇数長の路になります。
頂点について、がスタートから偶数長でたどり着ける頂点、がスタートから奇数長でたどり着ける頂点だと考えると 納得できると思います。
一般化
今回の問題では奇数長か偶数長かに注目すればいいですが、一般にの倍数長の最短路を考えるならば、頂点の数を倍に増やしたような グラフを考えればいいことがわかります。元のグラフの辺に対応して、新しいグラフで本の辺を張ってあげればいいですね。