Description
在Farmer Justin的农场中有许多灰化肥，它们都堆积在A仓库里。为了方便施肥，Farmer Justin需要修一些公路使得他能用拖拉机把这些灰化肥拉到其他仓库里。由于Farmer Justin及其懒惰，所以他只想一次拉完所有的灰化肥送到其他仓库里。但是灰化肥见光易挥发，所以Farmer Justin需要尽快把这些灰化肥拉完。现在告诉你Farmer Justin农场的构成地图，请你帮帮他计划一条从A仓库出发走完所有仓库的方案吧！由于Farmer Justin非常的讨厌浪费时间，所以你只需要告诉他最短的距离和走过所有农场的顺序。(注意:拖拉机走的时候是四联通的。)
Solution
状压DP+BFS
首先先暴力BFS跑出任意两个点之间的距离。
然后考虑DP，设$dp[i][j]$表示当前已经遍历过的点状态为$i$，最后一个遍历的点为$j$的最小值。
很明显：
$$dp[i][j]=dp[i\oplus (1<<k-1)][k]+cost[k][j](i\&(1<<k-1)!=0)$$
又因为要记录路径，于是开一个数组$g$与$dp$类似，更新的过程中记录下路径即可。
注意要开long long。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<bits/stdc++.h> #define int long long using namespace std; const int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; int r,c,n,cost[20][20],dis[510][510],Min,f[1<<16][16]; char a[510][510]; string Ans,g[1<<16][16]; struct node{int x,y;}G[20]; queue<node> q; inline void bfs(int x){ memset(dis,0,sizeof(dis)); while(!q.empty()) q.pop(); q.push(G[x]);dis[G[x].x][G[x].y]=1; while(!q.empty()){ node u=q.front();q.pop(); for(int i=0;i<4;i++){ int xx=u.x+dx[i],yy=u.y+dy[i]; if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&a[xx][yy]!='*'&&!dis[xx][yy]){ dis[xx][yy]=dis[u.x][u.y]+1; q.push((node){xx,yy}); } } } } signed main(){ scanf("%lld%lld%lld",&r,&c,&n); for(int i=1;i<=r;i++) cin>>a[i]+1; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if('A'<=a[i][j]&&a[i][j]<='Z') G[a[i][j]-'A'+1]=(node){i,j}; for(int i=1;i<=n;i++){ bfs(i); for(int j=1;j<=n;j++) cost[i][j]=dis[G[j].x][G[j].y]-1; } memset(f,63,sizeof(f)); f[1][1]=0; g[1][1]='A'; for(int i=2;i<(1<<n);i++){ if(!(i&1)) continue ; for(int j=1;j<=n;j++){ if(!(i&(1<<j-1))) continue ; for(int k=2;k<=n;k++){ if(!(i&(1<<k-1))||j==k) continue ; if(f[i][k]>f[i^(1<<k-1)][j]+cost[j][k]) f[i][k]=f[i^(1<<k-1)][j]+cost[j][k],g[i][k]=g[i^(1<<k-1)][j]+char(k+'A'-1); else if(f[i][k]==f[i^(1<<k-1)][j]+cost[j][k]&&g[i][k]>g[i^(1<<k-1)][j]+char(k+'A'-1)) g[i][k]=g[i^(1<<k-1)][j]+char(k+'A'-1); } } } Min=f[(1<<n)-1][2];Ans=g[(1<<n)-1][2]; for(int i=3;i<=n;i++) if(Min>f[(1<<n)-1][i]) Min=f[(1<<n)-1][i],Ans=g[(1<<n)-1][i]; else if(Min==f[(1<<n)-1][i]&&Ans>g[(1<<n)-1][i]) Ans=g[(1<<n)-1][i]; return printf("%lld\n",Min),cout<<Ans<<endl,0; } |
