F - The Shortest Statement

問題概要

頂点辺の連結な重み付き無向グラフが与えられる。個のクエリに答えよ。番目のクエリでは頂点間の最短距離を答えよ。

考えたこと

木っぽいグラフが与えられるということなので、とりあえず木に場合について考えてみることにする。 木の場合はまんまLCAを使うことができます。具体的には

1. 適当な1頂点を根として、根付き木を考える。この根から各頂点への最短距離をbfsでもして求めておく。
2. に対して、これらのLCAをで求め、それをとおく。
3. 間の最短距離は、である。

次はこれをいまのグラフに拡張してみましょう。 グラフから適切に辺を本削除すると木になります。 削除された辺につながっている頂点の集合をとします。

元のグラフ上での2頂点間の最短経路はもちろん削除された辺を通る場合があります。そこで、削除された辺も含めたの 中の任意の2頂点間の距離をワーシャルフロイドで事前計算しておきます。

このとき、間の最短距離は次のように計算することができます。

1. 最短距離を木上での最短距離で初期化します。
2. から木上を通ってまでいき、そこからに抜けて、 から木上を通ってに行く経路をすべてのの組み合わせについて計算し、最短距離を更新する

定数倍が重めですが、でこの問題を解くことができました。