题解 P4772 【灰化肥，会挥发】

· · 题解

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

定义状态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;
}