この問題はbitDPを用いて \(O((N+M)^2 2^{N+M})\) で解くことができます。

より基本的な類題：ABC180E『Traveling Salesman among Aerial Cities』

\(M=0\) の場合、次のようなDPで解くことができます。

\(DP[i][S]=\)現在地が街 \(i\) で、訪問済みの街の集合が \(S\) であるときの所要時間の最小値

\(DP[i][S]=\min\{DP[j][S\setminus \{i\}]+\mathrm{time}(i,j) \mid j\in S\setminus\{i\}\}\)
ただし、\(\mathrm{time}\) は街 \(i\) から街 \(j\) への所要時間を表す。

\(M>0\) の場合も、「宝箱も街と同様に扱い、宝箱は訪問せずに原点に戻っても良い」とすることで同様のDPで解くことができます。何個のブースターを拾っているかは \(S\) から判別可能なので、改めて情報を持つ必要はありません。

実装例(C)
実装例(Python)

なお、「訪問する宝箱の集合を固定し、\(2^M\) 通りそれぞれについて TSP を解く」とした場合、計算量は \(O((N+M)^2 2^N3^M)\) となります。高速な言語ではこちらの方針でも実行時間制限に間に合わせることができます。