問題

単純無向連結グラフ $G = (V, E)$ と部分集合 $S \subseteq V$ が与えられる。 異なる $2$ 頂点 $x, y \in S$ を選んでできるグラフ $G _ {x,y} = (V, E \cup \lbrace (x, y) \rbrace)$ 上の頂点 $1$ から頂点 $N$ への最短路長を $f(x, y)$ とする。 $\max _ {x, y \in S \wedge x \ne y} f(x, y)$ を求めよ。

解法

たぶん嘘

special な頂点の対 $(x, y)$ のいくつかを乱択 + heuristic で選んで試す。

それぞれの頂点 $v$ に対し始点からの距離 $s_v = d(1, v)$ と終点からの距離 $t_v = d(v, N)$ を求めておく。 special な頂点 $x, y$ をふたつ選んで使ったときの最短距離の値は $f(x, y) = \min \lbrace s_N, s_x + 1 + t_y, s_y + 1 + t_x \rbrace$ である。 答えは $\mathrm{ans} = \max \lbrace f(x, y) \mid x, y ~\text{are special}~ \wedge x \ne y \rbrace$ であるので、正解の対 $(x, y)$ を引ければよい。

とりあえず乱択する。$x, y$ 間に辺があれば正解確定なのでとりあえず確認しておく。 $s_x, s_y$ や $t_x, t_y$ が近い対 $(x, y)$ は正解に近い気がするのでこれも見ておく。 なぜか通る。

想定解

$s_x - t_y$ でソートして実家ぽく。計算量は BFS とソートが効いて $O(m + k \log k)$。

$f(x, y)$ の代わりに $g(x, y) = \min \lbrace s_x + t_y, s_y + t_x \rbrace$ を考えても同じである。 $\max g(x, y)$ を求れば $\mathrm{ans}$ も求まる。 そして $x, y$ の順序について、一般性を失うことなく $s_x + t_y \le s_y + t_x$ と仮定してよい。 つまり $\max \lbrace s_x + t_y \mid x, y \in S \wedge x \ne y \wedge s_x + t_y \le s_y + t_x \rbrace$ を求める問題に帰着された。

さて条件 $s_x + t_y \le s_y + t_x$ は $s_x - t_x \le s_y - t_y$ と同値である。 つまり $h(x) = s_x - t_x$ でソートし $h(x) \le h(y)$ な順序対 $(x, y)$ だけ考えればよい。 さて $h(x)$ の昇順に並べた $i$ 番目の頂点 $y$ まで見たとき $y$ は、$0, 1, \dots, i - 1$ 番目の頂点の中で最も $s_x$ の大きい $x$ と対にすればよい。 つまり $\max \left\lbrace \max \lbrace s_x \mid h(x) \le h(y) \wedge x \ne y \rbrace + t_y \mid y \in S \right\rbrace$ を計算する。 なお $h(x) = h(y)$ な組 $(x, y)$ については $s_x + t_y = s_y + t_x$ なのでその順序は気にしなくてよい。

メモ

リンク