魔法石を頂点、隣り合わせにできる組を辺として、無向グラフとして扱うことにします。

\(K ≤ 17\) と、 \(K\) の制約が非常に小さいことに注目しましょう。
頂点 \(C_1, C_2, \dots, C_K\) のみを見ると、この問題は最短ハミルトン路問題と同じ形をしています。
そこで動的計画法によって効率的に解くことを考えます。

集合 \(C\) を \(C = \{C_1, C_2, \dots, C_K\}\) 、\(S\) を \(C\) の部分集合、 \(i\) を \(S\) の要素として、

\(dp[S][i] = {}\)( \(S\) の各頂点を含み頂点 \(i\) で終わるパスの長さの最小値 )

とすると、問題の答えは \(\displaystyle \min_{i}\{dp[C][i]\} + 1\) です。
この DP は、\(\text{dist}(i, j)\) を頂点 \(i, j\) 間の距離として、

\(\displaystyle dp[\{i\}][i] = 0\)
\(\displaystyle dp[S][i] = \min_{j}\{dp[S \setminus \{i\}][j] + \text{dist}(i, j)\}\)

の漸化式で ( \(\text{dist}(i, j)\) が分かれば) 下位集合から順に求めることができます。

\(\text{dist}(i, j)\) については、 \(i, j \in C\) であるので、 \(C_1, C_2, \dots, C_K\) を始点とした \(K\) 回の BFS で前計算することができます。

よって、計算量 \(O(2^KK^2+K(N+M))\) でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc190/submissions/19761405
回答例 (Python) : https://atcoder.jp/contests/abc190/submissions/19825273