PKU 2907-Collecting Beepers

問題概要

N(<=10)個の物体が格子上のマスの上に置かれている。全てを回収して元の位置に戻るのにかかる最小の時間を求めよ。

解法

BitDPする。（10！）なので全探索でも間に合うかも…？

実装(C++)

#include <iostream>
#include <algorithm>
using namespace std;
#define chmin(a,b) a=min((a),(b))
int main(){
  int T;
  cin>>T;
  while(T--){
    int n,x[11],y[11],dp[11][1<<11];
    cin>>x[0]>>y[0];
    cin>>x[0]>>y[0];
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];n++;
    for(int i=0;i<n;i++)fill(dp[i],dp[i]+(1<<n),9999999);
    dp[0][0]=0;
    for(int i=0;i<1<<n;i++){
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
          if((i>>k)&1)continue;
          chmin(dp[k][i|(1<<k)],dp[j][i]+abs(x[k]-x[j])+abs(y[k]-y[j]));
        }
      }
    }
    cout<<"The shortest path has length "<<dp[0][(1<<n)-1]<<endl;
  }
}