Luogu P4772 灰化肥，会挥发 题解

#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;
}