洛谷P10422题（2023蓝桥杯国A）：状态压缩BFS在迷宫探险问题中的应用

一、题目解读

本题属于典型的图论与状态压缩结合题型，要求玩家在迷宫中移动时需考虑怪物击杀顺序对血量的影响。题目核心考察点包括：

1. 带状态的最短路径计算

2. 位运算表示怪物击杀状态

3. 动态规划与优先队列的结合使用

4. 实时伤害计算机制

二、解题思路

采用状态压缩+BFS+优先队列的复合算法：

1. 状态设计：四元组(当前节点, 击杀掩码, 剩余血量, 累计时间)

2. 剪枝优化：维护二维DP数组记录各状态最短时间

3. 伤害计算：根据相邻存活怪物实时扣除血量

4. 终止条件：到达终点且击杀全部怪物（掩码全1）

三、解题步骤

1. 输入处理：读取节点数N、边数M、初始血量HP

2. 特殊判断：处理单节点边界情况

3. 邻接表构建：存储带权无向图（过滤自环）

4. 状态初始化：从起点(0,0,HP,0)开始

5. 优先队列处理：

• 击杀当前怪物：更新掩码并计算相邻伤害

• 移动相邻节点：累加移动时间

6. 结果输出：首个满足终止条件的状态时间

四、完整代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct State {
    int node;       // 当前节点(0~N-1)
    int mask;       // 已击杀怪物状态(位掩码)
    int hp;         // 剩余血量
    int time;       // 已用时间
    
    bool operator>(const State& other) const {
        return time > other.time;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, HP;
    cin >> N >> M >> HP;
    
    if(N == 1) {  // 特殊情况处理：只有起点
        cout << (HP > 0 ? 0 : -1) << endl;
        return 0;
    }
    
    vector<int> attack(N);
    for(int i = 0; i < N; ++i) {
        cin >> attack[i];
    }
    
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if(u == v) continue;  // 过滤自环
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    
    // 预处理相邻节点
    vector<vector<int>> neighbors(N);
    for(int u = 0; u < N; ++u) {
        for(auto& edge : adj[u]) {
            neighbors[u].push_back(edge.first);
        }
    }
    
    // 初始化DP数组
    vector<vector<int>> min_time(N, vector<int>(1 << N, INT_MAX));
    priority_queue<State, vector<State>, greater<State>> pq;
    
    // 初始状态：节点0，未击杀，满血
    pq.push({0, 0, HP, 0});
    min_time[0][0] = 0;
    
    int result = -1;
    
    while(!pq.empty()) {
        State current = pq.top();
        pq.pop();
        
        // 终止条件：到达终点且击杀所有怪物
        if(current.node == N-1 && current.mask == (1 << N) - 1) {
            result = current.time;
            break;
        }
        
        // 非最优解跳过
        if(current.time > min_time[current.node][current.mask]) {
            continue;
        }
        
        // 尝试击杀当前怪物(如果未击杀)
        if(!(current.mask & (1 << current.node))) {
            int new_mask = current.mask | (1 << current.node);
            int damage = 0;
            
            // 计算相邻存活怪物伤害
            for(int neighbor : neighbors[current.node]) {
                if(neighbor != current.node && !(new_mask & (1 << neighbor))) {
                    damage += attack[neighbor];
                }
            }
            
            int new_hp = current.hp - damage;
            
            // 血量足够且新状态更优
            if(new_hp > 0 && current.time < min_time[current.node][new_mask]) {
                min_time[current.node][new_mask] = current.time;
                pq.push({current.node, new_mask, new_hp, current.time});
            }
        }
        
        // 尝试移动
        for(auto& edge : adj[current.node]) {
            int next_node = edge.first;
            int cost = edge.second;
            int new_time = current.time + cost;
            
            if(new_time < min_time[next_node][current.mask]) {
                min_time[next_node][current.mask] = new_time;
                pq.push({next_node, current.mask, current.hp, new_time});
            }
        }
    }
    
    cout << result << endl;
    return 0;
}

五、算法总结

本解法通过状态压缩将O(N!)的暴力搜索优化为O(N*2^N)的可行方案，亮点在于：

1. 位掩码应用：用int型变量表示2^N种击杀状态

2. 动态剪枝：dp数组避免重复计算相同状态

3. 实时伤害：通过预处理邻接表加速伤害计算

4. 优先队列：确保首次到达终止状态即为最优解