読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

POJ 2907 : Collecting Beepers

POJ 巡回セールスマン問題

問題リンク : 2907 -- Collecting Beepers

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

解法:
巡回セールスマン問題そのまま
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;
}