解説なさそう？というわけで。

次の手順で解けます。計算量解析のため、magical bridge の本数に \(1\) を加えた値を \(B (\leq 101)\) とします。

magical bridge を使う本数ごとの、最短距離の計算

\(S_i-T\) 間について、ちょうど \(n\) 本の magical bridge を通るときの最短距離 \(\text{dist}_i[n]\) を計算します。 これは、\(NB\) 頂点 \(MB\) 辺からなるグラフについて dijkstra 法を用いることで計算できます。

\(S_1, S_2\) それぞれを始点として計算してもよいですが、\(T\) を始点とすると dijkstra 法 1 回でよいです。

距離関数の理解

magical bridge の長さを \(x\) とした場合の \(S_i-T\) 間の距離を、\(f_i(x)\) と書きましょう。\(f_i(x) = \min_{0\leq n\leq B} (nx + \text{dist}_i[n])\) となり、\(B\) 個の アフィン関数の \(\min\) であることが分かります。（アフィン関数とは、 \(x\mapsto ax + b\) の形の関数。\(a=0\) も認めている）

これは、区間ごとにアフィン関数です。どのような区間においてどのようなアフィン関数であるかは、Convex Hull Trick という典型アルゴリズムにより求めることができます。

答の計算

\(f_1, f_2\) に対する傾きの変化点をマージすると、非負実数全体は次のような区間 \([L_k, R_k)\) に分割できます。

• \([L_k,R_k)\) 上、\(f_1, f_2\) はともにアフィン関数である。

求めるものは、\(\min_{x\geq 0} |f_1(x)-f_2(x)|\) ですが、これは各区間 \([L_k, R_k)\) における \(\min\) を求めて、その最小値をとることで計算できます。

各区間における計算は、結局 \(\min_{L\leq x < R} |ax+b|\) の形の計算に帰着されます。あとは、 \(x\) が整数のみをとるというところに注意しながらこれを処理してあげましょう。

具体的には、最小値の候補点として、\(x=L, R-1\) および \(\frac{-b}{a}\) の前後という \(O(1)\) 個の点の値を調べればよいです。これだと \(a = 0\) のときがまずいですが、それは場合分けで用意に処理できます。

計算量解析

\(NB\) 頂点 \(MB\) 辺の dijkstra 法は、\(O((NB+MB)\log(NB+MB))\) 時間で行えます。 後半部分は、既に傾きでソートされた \(O(B)\) 個のアフィン関数を処理するだけで、\(O(B)\) 時間です。結局、問題を解くために必要な計算量は \(O((NB+MB)\log(NB+MB))\) 時間です。

データセット数が不明なので、\((NB+MB)\log(NB+MB)\) のデータセットに対する総和が全く見積もれない謎問題ですが、これで余裕を持って AC になるようです。

提出 + assert で調べたところ、

• データセット数は約 130 件
• \(\sum (NB+MB)\log_2(NB+MB) \leq 10^8\)

程度になっているようです。