自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:03:28，当前版本为作者最后更新于2018-07-19 14:52:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先发现这道题的仓库数量偏小，考虑状压。

定义状态$f[i][j]$表示已经走过的仓库集合为$i$且最后一次到的仓库为$j$时走过的最小距离。

这个转移的话只需要在枚举下一个到达的仓库$k$就可以很方便的转移了。如下:

$ f[i|(1<<k)][k] =min(f[i|(1<<k)][k], f[i][j] + dis[j][k])$

这里的$dis[j][k]$就表示从$j$到$k$的最短路，这个只需要在原图中以每一个仓库为起点跑几遍$BFS$就可以了。

但是我们还需要考虑输出字典序最小的方案。

这个其实并不难，只需要类比地再记录一个状态$g[i][j]$表示最小距离情况下的最小字典序的方案即可。

有很多人WA就是只考虑在转移$f$的时候顺便更新一下$g$，殊不知需要在$f$相等的时候再判断一下更新$g$看看会不会有更小的字典序产生。

具体细节请看丑陋的代码

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int x;
    int y;
};

const int N = 16;
const int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//四个方向

int n;
int m;
int s;
int jsq;
int f[1 << N][N];    //最小的距离 
string g[1 << N][N]; //走的方案
int To[N][N];        //最短路
int Arrive[501][501];//记录以某一个点开始到所有点的最短路
char S[501][501];    //存地图

Node F[N];

void BFS(Node F) {  //求从F仓库开始到其他仓库的最短路是多少
	memset(Arrive, 0, sizeof(Arrive));
	queue<Node>q;
	q.push(F);
	Arrive[F.x][F.y] = 1;
	while(!q.empty()) {
		Node f = q.front(); q.pop();
		for(int i = 0; i < 4; i++) {
			int x = f.x + fx[i][0];
			int y = f.y + fx[i][1];
			if(x < 1 || y < 1 || x > n || y > m || S[x][y] == '*' || Arrive[x][y]) continue;  //不可以走到就跳过
			Arrive[x][y] = Arrive[f.x][f.y] + 1; //更新最短路
			q.push((Node){x, y});  //加入队列
		}
	}
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n; i++)
        scanf("%s", S[i] + 1); //读入地图
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) //找到仓库点
            if(S[i][j] >= 'A' && S[i][j] <= 'Z')
                F[S[i][j] - 'A' + 1] = (Node){i, j};
    for(int i = 1; i <= s; i++) { //求出最短路
		BFS(F[i]);
		for(int j = 1; j <= s; j++) To[i][j] = Arrive[F[j].x][F[j].y] - 1;
	}
	memset(f, 63, sizeof(f));  //初始化
	f[1][1] = 0;
	g[1][1] = "A";  //只能从A号仓库开始
	for(int i = 2; i < (1 << s); i++) {
		if(!(i & 1)) continue;
		for(int j = 1; j <= s; j++) {
			if(i & (1 << (j - 1)) == 0) continue;
			for(int k = 2; k <= s; k++) {
				if(i & (1 << (k - 1)) == 0 || j == k) continue;
				if(f[i][k] > f[i ^ (1 << (k - 1))][j] + To[j][k]) {
					f[i][k] = f[i ^ (1 << (k - 1))][j] + To[j][k];
					g[i][k] = g[i ^ (1 << (k - 1))][j] + (char)(k + 'A' - 1);
				} //如果可以有更小的f更新就直接更新
				else if(f[i][k] == f[i ^ (1 << (k - 1))][j] + To[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));   
                    //如果f相等就考虑字典序会不会更新之后更小
			}
		}
	}
	int T = (1 << s) - 1;
	int Min = f[T][2];
	string res = g[T][2];  //不可能最后一个点到A仓库，所有从第二个仓库开始
	for(int i = 3; i <= s; i++) {
		if(Min > f[T][i]) {
			Min = f[T][i];
			res = g[T][i];
		}
		else if(Min == f[T][i] && res > g[T][i])
			res = g[T][i];
	}//寻找最优解
	printf("%d\n", Min);
	cout << res << endl;
    return 0;
}