PKU 2907 Collecting Beepers

http://poj.org/problem?id=2907
部屋にロボットがいて、そこに散らばっている10個以下のポケベルを回収する。
この時、あるスタート地点から全てを回収してまたスタート地点に戻ってくるのに必要な最短の移動距離を求めろというような問題。

訪れたノードを保持してダイクストラ。
bitDPはかけないです。

bool vis[10][1<<10];
int cost[10][10];
PI xy[10];

main(){
  int T;
  cin>>T;
  while(T--){
    memset(vis,0,sizeof(vis));
    int sx,sy;
    cin>>sx>>sy;
    cin>>sx>>sy;
    int n;
    cin>>n;
    priority_queue<pair<int,PI> >q;    
    rep(i,n){
      cost[i][i]=0;
      cin>>xy[i].F>>xy[i].S;
      q.push(mp(-abs(xy[i].F-sx)-abs(xy[i].S-sy),mp(1<<i,i)));
    }
    int ans=1<<24;
    while(!q.empty()){
      int cc=-q.top().F,cst=q.top().S.F,cv=q.top().S.S;
      q.pop();
      if(vis[cv][cst])continue;
      vis[cv][cst]=true;
      if(cst==(1<<n)-1){
        ans=min(ans,cc+abs(sx-xy[cv].F)+abs(sy-xy[cv].S));
        continue;
      }
      rep(i,n){
        if(vis[i][cst|1<<i] || ((cst>>i)&1))continue;
        int nc=cc+abs(xy[i].F-xy[cv].F)+abs(xy[i].S-xy[cv].S);
        int nst=cst|1<<i;
        int nv=i;
        q.push(mp(-nc,mp(nst,nv)));
      }
    }
    printf("The shortest path has length %d\n",ans);
  }
}