ライブ会場のある都市の集合から \(1\) と \(N\) を除いたものを \(L\) とします．すなわち \(L = \{A_2, A_3, \ldots, A_{K-1}\}\) です．この \(L\) を用いると，この問題は「\(L\) に含まれる都市を \(2\) つ以上通って \(1\) から \(N\) へ行くときの最短距離」を求める問題と言い換えられます．

「\(L\) の頂点をいくつ通ったか」という情報を付加したグラフ上でダイクストラ法を行いたくなりますが，同じ頂点を \(2\) 度通ってしまう場合を回避する必要があります．

ここで，最適解（の \(1\) つ）が \(1, u, v, N\) でライブを行う全国ツアーであるとします．

\(S \cup T = L, S\cap T = \emptyset\) となるように \(S, T\) を取ります．すると「\(S\) に属する頂点と \(T\) に属する頂点をそれぞれ \(1\) つ以上通るときの最短距離」は，「\(S\) に属する頂点を通ったか」および「\(T\) に属する頂点を通ったか」という情報を付加した頂点数 \(4\) 倍のグラフにダイクストラ法を用いることで求められます．\(u\in S\) かつ \(v\in T\)（もしくは \(u\in T\) かつ \(v\in S\) ）であれば，この方法で求めた解が元問題の解です．

このままでは \(u, v\in S\)（もしくは \(u, v\in T\)）の場合を考慮できていません．そこで，この \(\{S, T\}\) の分割をいくつも試すことにします．試す分割を \(\{S_1, T_1\}, \{S_2, T_2\}, \ldots\) としたとき，ある \(k\) が存在して \(u\in S_k\) かつ \(v\in T_k\) が満たされれば最適解を求めることができます．すなわち，\(i, j\in L, i\neq j\) を満たすすべての \((i, j)\) について，ある \(k\) が存在して \(i\in S_k\) かつ \(j\in T_k\) であればよいです．

あとは上記の条件を満たすような \(L\) の分割の列を与えればよいです．例えば以下のような分割により条件を達成できます：

• \(S_k := \{i\in L \mid i\) の \(k\) bit 目は \(0\},\ T_k := \{i\in L \mid i\) の \(k\) bit 目は \(1\}\)

\(k\) は \(\lceil \log_2 N \rceil\) まで考えれば十分です．これにより本問題を \(\mathrm{O}((N+M)\log^2 N)\) 程度の時間計算量で解くことができます．

実装例