POJ 2907 : Collecting Beepers

問題リンク : 2907 -- Collecting Beepers

問題概要：
H*Wのグリッドが存在する
そのグリッド上のある点から指定された複数の点を全て任意の順番で訪れ、最終的にまた最初の点に戻ってくるまでの最小移動回数を求めよ
点は最大１０まで指定される

解法：
巡回セールスマン問題そのまま
dp[これまでに訪れた点の情報をビットで管理][今いる点] := 最小移動回数
としてビットDP

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

int main()
{
  int T,H,W,x0,y0;
  scanf("%d",&T);
  while(T--)
    {
      scanf("%d %d",&H,&W);
      scanf("%d %d",&x0,&y0);
      int n,mex;

      scanf("%d",&n);

      int x[n+1],y[n+1];
      x[0] = x0, y[0] = y0;
      for(int i=0;i<n;i++)scanf("%d %d",&x[i+1],&y[i+1]);
      n++;

      int dp[(1<<n)][n];
      rep(i,(1<<n))rep(j,n)dp[i][j] = inf;
      dp[1][0] = 0;

      rep(state,(1<<n))
	{
	  rep(cur,n)
	    {
	      if(!((state >> cur) & 1))continue;
	      if(dp[state][cur] == inf)continue;
	      rep(dest,n)
		{
		  if((state >> dest) & 1)continue;//already visited

		  dp[state|(1<<dest)][dest] = min(dp[state|(1<<dest)][dest],
						  dp[state][cur] + abs(x[cur]-x[dest])+abs(y[cur]-y[dest]));
		}
	    }
	}

      int ans = inf;
      rep(i,n)ans = min(ans,
			dp[(1<<n)-1][i]+abs(x[i]-x[0])+abs(y[i]-y[0]));

      printf("The shortest path has length %d\n",ans);

    }
  return 0;
}