最短ハミルトンパス

ライブラリ
  • 頂点数は17以下を想定
  • 隣接行列を与えるとパスを返す関数
// ハミルトンパスが存在するなら返す
// （無いなら空の配列を返す）
// 入力 G : 隣接行列 (adjacency matrix)
// 参考にした : by tatyam
//   atcoder.jp/contests/abc190/submissions/19761405
VI Get_Hamiltonian_Path(VV G){
  ll N = G.size();
  assert(N<30);
  // dp[flag][last]
  // flag : visit flags
  // last : last position
  VV dp(1<<N, VI(N,inf));
  rep(i,N){
    dp[1<<i][i]=0; // 始点のみ訪れた場合
  }
  FOR(after,1,1<<N){
    rep(i,N) if(after & 1<<i){ // iを削る
      ll before = after ^ 1<<i;
      rep(j,N) if(before & 1<<j){
        // beforeの状態でラストがjの点から、iへの遷移
        chmin(dp[after][i], dp[before][j] + G[j][i]);
      }
    }
  }
  ll min_len = inf;
  ll min_last = -1;
  rep(i,N){
    ll all = (1<<N)-1;
    if(dp[all][i] < min_len){
      min_len = dp[all][i];
      min_last = i;
    }
  }
  if(min_len==inf){
    VI path; return path;
  }
  // 復元
  VI path = {min_last};
  ll visit = (1<<N)-1;
  ll last = min_last;
  ll len = min_len;
  while(len){
    rep(i,N) if(visit & 1<<i){
      // iからlastに来たかどうか
      if(i==last)continue;
      ll before = visit ^ (1<<last);
      if(dp[before][i] + G[i][last] == dp[visit][last]){
        // iから来たんだね
        visit = before;
        len -= G[i][last];
        last = i;
        path.push_back(i);
        break;
      }
    }
  }
  reverse(ALL(path));
  return path;
}

verified