この問題は巡回セールスマン問題としてよく知られている問題であり、 bitDP により解くことができます。

まずワーシャルフロイド法などを用い「町 \(i\) から町 \(j\) へ最短時間」を求めておき、\(C_{i,j}\) とします。

「次に初めて訪れる町」を順に考えることで問題は「町 \(2,3,\dots, N\) の \(N-1\) 個の町を適当な順に並べて \(P_1,P_2,\dots,P_{N-1}\) とするとき、\(C_{1,P_1}+C_{P_1,P_2}+\dots+C_{P_{N-2},P_{N-1}}+C_{P_{N-1},1}\) を最小化せよ」となります。

\(\mathrm{DP}[S][i]\) を「訪問済みの町の集合(※)が \(S\) で、町 \(i\) にいる状態になるまでの最短時間」と定めます（※スタート地点の町 \(1\) は含まず、ゴール地点の町 \(1\) は含む）。 次にどの町に行くかを考える配るDPにより

\(\mathrm{DP}[S\cup\{j\}][j]\leftarrow\min(\mathrm{DP}[S\cup\{j\}][j], \mathrm{dp}[S][i]+C_{i,j})\)

と更新することができます。初期値は \(\mathrm{DP}[\emptyset][1]\) のみ \(0\) で、それ以外は \(\infty\) とします。

このDPでは、更新先の \(S\) が必ず大きくなるため、\(S\) の大きさが小さい順に計算することでこの DP テーブルを埋めることができます。答えは \(\mathrm{DP}[\{1,2,\dots,N\}][1]\) となります。

状態数が \(O(N2^N)\) 、遷移が \(O(N)\) 通りあるため DP の計算には \(O(N^22^N)\) 時間かかります。

実装の工夫

以上までの説明でこの問題を解くことは可能ですが、 DP のキーとして集合を持つことや、要素数の小さい順に DP テーブルを埋めるのは実装が複雑になる傾向にあります。以下ではより簡潔な実装を紹介します。

説明の都合上、町の添字を \(1\) ずらして、町 \(0,1,\dots,N-1\) とします。

「\(0\) 以上 \(N\) 未満の整数からなる集合」は、\(\sum_{i\in S}2^i\) により「\(0\) 以上 \(2^N\) 未満の整数」に1対1に対応させることができます。これにより集合 \(S\) と対応する整数を \(X_S\) と表すことにします。プログラミング的には、\(i\) が \(S\) に入っていることと、\(X_S\) の \(i\)-bit 目が \(1\) であることは同値となります。

この対応により、 DP のキーとして持つものが集合ではなく整数となるため、実装が容易になります。さらにこの対応において、 2 つの集合 \(S,T\) に対して、\(S\subset T\) ならば \(X_S\leq X_T\) となります。よって、 DP テーブルの更新を「\(S\) のサイズの昇順」ではなく「\(X_S\) の昇順」で行うことができるようになります。

競技プログラミングにおいては、集合を扱う DP のことを、以上の工夫まで含めて bitDP と呼びます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  int INF = 1e9;
  vector<vector<int>>G(n, vector<int>(n, INF));
  for(int i=0; i<n; i++) G[i][i] = 0;
  for(int i=0; i<m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u][v] = w;
    G[v][u] = w;
  }

  for(int k=0; k<n; k++){
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }

  vector<vector<int>>dp(1<<n, vector<int>(n, INF));
  dp[0][0] = 0;
  for(int s=0; s<1<<n; s++){
    for(int v=0; v<n; v++){
      for(int vv=0; vv<n; vv++){
        dp[s^(1<<vv)][vv] = min(dp[s^(1<<vv)][vv], dp[s][v] + G[v][vv]);
      }
    }
  }

  if(dp[(1<<n)-1][0] != INF){
    cout << dp[(1<<n)-1][0] << endl;
  }else{
    cout << -1 << endl;
  }
}

実装例 (Python)

N, M = map(int, input().split())
INF = 10**9
G = [[INF] * N for _ in range(N)]
for i in range(N):
  G[i][i]=0
for _ in range(M):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  G[u][v] = w
  G[v][u] = w

for k in range(N):
  for i in range(N):
    for j in range(N):
      G[i][j] = min(G[i][j], G[i][k] + G[k][j])

dp=[[INF] * N for _ in range(1<<N)]

dp[0][0] = 0
for s in range(1<<N):
  for v in range(N):
    for vv in range(N):
      dp[s^(1<<vv)][vv] = min(dp[s^(1<<vv)][vv], dp[s][v] + G[v][vv])

if dp[(1<<N)-1][0] != INF:
  print(dp[(1<<N)-1][0])
else:
  print(-1)