题目地址：FZU 2186 这题是很基础的TSP状压，，各个点之间的距离要先用BFS预处理出来。 这题在写memset(dp,INF,sizeof(dp));时，写成了memset(dp,INF,sizeof(d));。。。 调试了好长时间。。无语了。。。最近的状态太不行了。。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=300000+10;int d[13][13], dp[1<<12][13], n, m;int mp[110][110], vis[110][110];int jx[]={0,0,1,-1};int jy[]={1,-1,0,0};struct node{int x, y, step;};void bfs(int x, int y, int z){queue<node>q;node f1, f2;f1.x=x;f1.y=y;f1.step=0;q.push(f1);memset(vis,0,sizeof(vis));vis[x][y]=1;while(!q.empty()){f1=q.front();q.pop();if(mp[f1.x][f1.y]>0) d[z][mp[f1.x][f1.y]]=f1.step;for(int i=0;i<4;i++){f2.x=f1.x+jx[i];f2.y=f1.y+jy[i];if(f2.x>=0&&f2.x<n&&f2.y>=0&&f2.y<m&&!vis[f2.x][f2.y]&&mp[f2.x][f2.y]>=0){vis[f2.x][f2.y]=1;f2.step=f1.step+1;q.push(f2);}}}}int main(){int i, j, cnt, tot, tmp, k, ans;while(scanf(“%d%d”,&n,&m)!=EOF){cnt=0;for(i=0;i<n;i++){for(j=0;j<m;j++){scanf(“%d”,&mp[i][j]);if(mp[i][j]>0&&i+j) mp[i][j]=++cnt;}}if(mp[0][0]<0){puts(“-1”);continue ;}if(!cnt){puts(“0”);continue ;}mp[0][0]=0;memset(d,INF,sizeof(d));bfs(0,0,0);for(i=0;i<n;i++){for(j=0;j<m;j++){if(mp[i][j]>0){bfs(i,j,mp[i][j]);}}}tot=1<<cnt;memset(dp,INF,sizeof(dp));for(i=1;i<tot;i++){for(j=0;j<cnt;j++){if(i&(1<<j)){tmp=i-(1<<j);if(tmp==0){dp[i][j+1]=d[0][j+1];continue ;}for(k=0;k<cnt;k++){if(tmp&(1<<k)){dp[i][j+1]=min(dp[i][j+1],dp[tmp][k+1]+d[k+1][j+1]);}}}}}ans=INF;for(i=1;i<=cnt;i++){ans=min(ans,dp[tot-1][i]+d[0][i]);}if(ans==INF) puts(“-1”);else printf(“%d\n”,ans);}return 0;}
不论你在什么时候结束，重要的是结束之後就不要悔恨
