（2023蓝桥杯国A）洛谷P10422题解：基于状态压缩DP与优先队列的图论优化算法解析
一、题目解读
洛谷P10422题描述了一个包含N个节点的图，每个节点可能存在怪物，玩家需从起点出发，击杀所有怪物并抵达终点，同时需考虑血量消耗与时间限制。题目要求计算最小耗时，若无法完成则输出-1。核心挑战在于如何高效处理节点状态（怪物存活/击杀）与路径选择，兼顾血量动态变化。
二、解题思路
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;
}五、总结
本文通过状态压缩DP将多维状态降维，优先队列有效优化搜索路径，结合剪枝策略大幅降低时间复杂度。关键点包括：
1. 位掩码的巧妙运用，简化怪物状态管理；
2. 优先队列与DP表的协同剪枝，避免无效扩展；
3. 边界条件（如N=1、自环）的预处理提升鲁棒性。
该解法为图论与动态规划结合的典型案例，对解决同类问题具有重要参考价值。
原创内容 转载请注明出处
