AtCoder ABC 180 E - Traveling Salesman among Aerial Cities

問題

E - Traveling Salesman among Aerial Cities

解法

巡回セールスマン問題。

ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。

そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約下では十分間に合う。

dp配列定義

dp[訪れた都市の集合(bitで表現)][今いる都市番号] = 最小コスト
// 集合はbitで表現する.
// bitのn桁目が0だとn都市は未訪問、1だと訪問済

dpの更新

// 訪れた都市集合が i のとき、j 都市から k 都市への移動
dp[ i|1<<k ][k] = min(
  dp[ i|1<<k ][k],
  dp[i][j] + cost[i][j]
);  

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
template<class T>bool chmin(T &a,const T &b) {if(b<a){a=b; return 1;} return 0;}
const int INF = 1e9;

int main() {
  int n; cin >> n;
  int x[n],y[n],z[n];
  REP(i,n) cin >> x[i] >> y[i] >> z[i];

  // dp定義: [訪れた都市集合][今いる都市] = 最小コスト
  // 訪れた都市集合はbitで表現する
  // INF(十分大きい値)で初期化する
  vector<vector<int>> dp(1<<n,vector<int>(n,INF));

  // 都市iから都市jへのコストを事前計算
  int cost[n][n];
  REP(i,n) REP(j,n) {
    int c1 = abs(x[j]-x[i]);
    int c2 = abs(y[j]-y[i]);
    int c3 = max(0,z[j]-z[i]);
    cost[i][j] = c1+c2+c3;
  }

  // 開始点0から各都市への移動
  REP(i,n) {
    // 0から0への移動はスキップ
    if (i==0) continue;
    dp[1<<i][i] = cost[0][i];
  }

  REP(i,1<<n) {
    REP(j,n) {
      // j都市のフラグが立っていない場合
      // 未訪問のj都市からは移動できないのでスキップ
      if (~i>>j&1) continue;
      REP(k,n) {
        // k都市のフラグが立っている場合
        // 訪問済みなのでスキップ
        if (i>>k&1) continue;
        chmin(dp[i|1<<k][k], dp[i][j]+cost[j][k]);
      }
    }
  }

 // 全てに訪問済みで今いる都市が0(開始点に戻ってきている)の最小コスト
  cout << dp[(1<<n)-1][0] << endl;
}