以下のようなグラフを構築したときの、頂点 \(M_1\) から頂点 \(M_N\) までの最短距離が答えとなります。

• 頂点 \(I_1, \dots, I_N, M_1, \dots, M_N, O_1, \dots, O_N\) を用意する。
• \(I_i\) から \(M_i\)、\(M_i\) から \(O_i\) にそれぞれコスト \(c_i\) の辺を張る。
• \(\min (|x_i - x_j|, |y_i -y_j|) \leq K\) であるような \(i, j\) に対し、\(O_i\) から \(I_j\) にコスト \(0\) の辺を張る。

\((x_i, i)\) を std::set などのデータ構造に格納しておくことで、\(i\) が与えられたときに \(|x_i - x_j| \leq K\) であるような \(j\) を列挙することができます。\(y_i\) についても同様です。前述の方法でグラフを構築したとき、\(O_i\) から \(I_j\) に向かう辺の本数は最大で \(\Theta(N^2)\) となってしまいますが、各 \(I_j\) に対し、実際に必要な辺は以下の二通りのみです。

• \(|x_i - x_j| \leq K\) となる \(i\) の中で \(O_i\) までの距離が最短であるものについての \(O_i\) から \(I_j\) の辺
• \(|y_i - y_j| \leq K\) となる \(i\) の中で \(O_i\) までの距離が最短であるものについての \(O_i\) から \(I_j\) の辺

次に示すような工夫を施したダイクストラ法を行うことで高速に計算することができます。

頂点 \(O_i\) を取り出したとき、

• \(|x_i - x_j| \leq K\) を満たす \(j\) を列挙し、\(I_j\) までの距離を更新したのち、\((x_j, j)\) をデータ構造から削除する。
• \(|y_i - y_j| \leq K\) を満たす \(j\) を列挙し、\(I_j\) までの距離を更新したのち、\((y_j, j)\) をデータ構造から削除する。

各頂点について最短距離が更新されうる回数は高々 \(2\) 回なので、\(O(N \log N)\) でこの問題を解くことができました。