题意：
裸的tsp。
分析：
用bfs求出任意两点之间的距离后可以暴搜也可以用next_permutation水，，但效率肯定不如状压dp。dp[s][u]表示从0出发访问过s集合中的点，目前在点u走过的最短路程。
代码：
//poj 2688//sep9#include <iostream>#include <queue>using namespace std;const int maxW=32;const int maxN=12;int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};char graph[maxW][maxW];int g[maxW][maxW];int vis[maxW][maxW];int d[maxN][maxN];int n,w,h;int dp[1<<maxN][maxN];struct Node{int x,y;}dirty_pnt[maxN];void bfs(int s){memset(vis,-1,sizeof(vis));queue<Node> Q;Q.push(dirty_pnt[s]);vis[dirty_pnt[s].x][dirty_pnt[s].y]=0;while(!Q.empty()){Node q=Q.front();Q.pop();int x=q.x,y=q.y;for(int i=0;i<4;++i){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0&&nx<h&&ny>=0&&ny<w&&g[nx][ny]>=0&&vis[nx][ny]==-1){vis[nx][ny]=vis[x][y]+1;Node p;p.x=nx,p.y=ny;Q.push(p);}}}} int rec(int s,int u){if(dp[s][u]!=-1)return dp[s][u];int i,j,res=INT_MAX;int ss=s&(~(1<<u));for(i=0;i<n;++i)if(ss>>i&1)res=min(res,rec(ss,i)+d[i+1][u+1]);return dp[s][u]=res;}int main(){int i,j,k;while(scanf("%d%d",&w,&h)==2&&(w+h)){for(i=0;i<h;++i)scanf("%s",graph[i]);n=0;for(i=0;i<h;++i)for(j=0;j<w;++j){if(graph[i][j]=='*'){g[i][j]=++n;dirty_pnt[n].x=i;dirty_pnt[n].y=j;}else if(graph[i][j]=='.')g[i][j]=0;else if(graph[i][j]=='o'){g[i][j]=0;dirty_pnt[0].x=i;dirty_pnt[0].y=j;}elseg[i][j]=-1;}int not_reach=0;for(k=0;k<=n&&!not_reach;++k){bfs(k);for(i=0;i<=k;++i){d[k][i]=d[i][k]=vis[dirty_pnt[i].x][dirty_pnt[i].y];if(d[k][i]==-1){not_reach=1;break;}}}//for(i=0;i<=n;++i)//for(j=0;j<=n;++j){//printf("%d %d==%d\n",i,j,d[i][j]);//}if(not_reach==1){printf("-1\n");continue;}memset(dp,-1,sizeof(dp));int ans=INT_MAX;for(i=0;i<n;++i)dp[1<<i][i]=d[0][i+1];for(i=0;i<n;++i)ans=min(ans,rec((1<<n)-1,i));printf("%d\n",ans);}return 0;}
别人失去了信心，他却下决心实现自己的目标。
