当前位置：首页 > 蓝桥杯 > （2023蓝桥杯国A）洛谷P10422题解：基于状态压缩DP与优先队列的图论优化算法解析

（2023蓝桥杯国A）洛谷P10422题解：基于状态压缩DP与优先队列的图论优化算法解析

2天前

一、题目解读

洛谷P10422题描述了一个包含N个节点的图，每个节点可能存在怪物，玩家需从起点出发，击杀所有怪物并抵达终点，同时需考虑血量消耗与时间限制。题目要求计算最小耗时，若无法完成则输出-1。核心挑战在于如何高效处理节点状态（怪物存活/击杀）与路径选择，兼顾血量动态变化。

二、解题思路

用状态压缩动态规划（DP）结合优先队列优化的策略：

1. 状态表示：定义State结构体，包含当前节点、怪物击杀状态（位掩码）、剩余血量与时间，利用位运算高效记录怪物状态。

2. 优化搜索：通过优先队列（最小堆）维护当前最优时间节点，避免冗余路径扩展（A*思想）。

3. 动态转移：遍历邻居节点时，分情况处理：击杀怪物（更新位掩码与血量）、直接移动，取最优时间更新DP表。

4. 边界与特例：N=1时直接判断血量，过滤自环边减少无效计算。

三、解题步骤

1. 输入与预处理：

○ 读取N（节点数）、M（边数）、HP（初始血量），并存储节点攻击力与边信息。

○ 构建邻居列表neighbors，预处理节点可达关系。

2. 初始化DP与队列：

○ 定义min_time[node][mask]记录节点+状态的最短时间，初始值为INT_MAX。

○ 将起点状态（节点0、未击杀、满血、时间0）入队，并初始化DP[0][0]=0。

3. 核心循环：

○ 弹出队首状态，若满足终点+全击杀条件，终止并返回时间。

○ 若当前状态非最优（时间>DP值），跳过（剪枝）。

○ 尝试击杀当前节点怪物：更新位掩码与新血量，计算时间增量并更新DP。

○ 遍历邻居节点：转移至新节点，扣除移动时间，更新DP并入队。

4. 结果判定：循环结束后，若未找到可行解，返回-1。

四、代码与注释

#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); // 加快IO速度

    int N, M, HP;
    cin >> N >> M >> HP;
    if(N == 1) {  // 特判：仅起点时，血量足够则耗时0
        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); // 邻接表存储边(u, v, w)
    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);
        }
    }

    vector<vector<int>> min_time(N, vector<int>(1 << N, INT_MAX)); // DP表初始化
    priority_queue<State, vector<State>, greater<State>> pq; // 优先队列

    // 初始状态入队
    pq.push({0, 0, HP, 0});
    min_time[0][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(int next : neighbors[current.node]) {
            int new_time = current.time + adj[current.node][next].second; // 移动耗时
            if(new_time >= min_time[next][current.mask]) continue; // 剪枝
            min_time[next][current.mask] = new_time;
            pq.push({next, current.mask, current.hp, new_time});
        }
    }
    cout << result << endl;
    return 0;
}