题解：P10422 [蓝桥杯 2023 国 A] 迷宫探险
a_cow_of_FJ
·
·
题解
本题思路十分暴力：拆点 + 状态压缩 + dijkstra
估计是最慢的一篇题解了。
题意
### 注意：
1. 经过节点时可以选择**击杀**当前怪物并受到伤害（如果该怪物还活着），也可以选择**不击杀**继续去别的点，且不会受到任何伤害。
2. 击杀所有怪物并且到终点时血量必须**大于 $0$**。
## 思路
首先很明显是最短路。但是由于有血量和怪物的限制，需要拆点。这里重点考虑状态设计。
由于每个怪物最多杀一次，又观察到 $1≤N≤15$，所以考虑状态压缩。
具体地说，把每个怪物的击杀情况压缩成一个二进制串，若从右往左数第 $i$ 位为 $1$，则第 $i$ 个点上的怪物已经被击杀；否则这个怪物还活着。
于是点就可以这么拆：
设 $dis[i][hp][S]$ 表示到达点 $i$ 时还剩 $hp$ 点血，并且怪物击杀状态为 $S$，所花的最少时间。
空间复杂度即为 $O(n \cdot HP \cdot 2^n)$，本题内存限制为 $512$ MB，空间上足以承受。
话说回来，最后跑一遍堆优化的 dijkstra，答案即为：
$$
\min\limits_{hp>0} dis[n-1][hp][2^n-1]
$$
还有一点，就是不同击杀状态下击杀每个点的怪物所受到的伤害可以预处理出来（$damage[u][S]$ 表示击杀状态为
$S$ 下击杀点 $u$ 所受伤害，前提得保证击杀前 $u$ 还活着）：
```cpp
for (int u = 0; u < n; u++)
for (int S = 0; S < 1 << n; S++)
for (Edge e : G[u])
damage[u][S] += !(S & 1 << e.v) * d[e.v];
```
最坏情况下时间复杂度为 $O(n^3 \cdot HP \cdot 2^n)$，但实际上远没有那么高。
## 代码
```cpp
#include <iostream>
#include <vector> // 邻接表存图
#include <cstring> // memset
#include <queue> // 优先队列
using namespace std;
const int MAXN = 15, MAXHP = 100 + 2;
int n, m, HP;
int d[MAXN], damage[MAXN][1 << MAXN];
struct Edge { int v, w; };
vector<Edge> G[MAXN];
struct Node
{
int u, hp, S, dis; // 当前节点、血量、击杀状态、所花时间
friend bool operator<(Node a, Node b) { return a.dis > b.dis; }
};
int dis[MAXN][MAXHP][1 << MAXN];
void dijkstra()
{
//初始化
memset(dis, 63, sizeof dis);
dis[0][HP][0] = 0;
priority_queue<Node> q;
q.push({ 0, HP, 0, 0 });
while (!q.empty())
{
auto [u, hp, S, dist] = q.top(); q.pop(); // auto [...] = ... 不是啥好习惯，但是蒟蒻用惯了
if (dist > dis[u][hp][S]) continue;
if (~S & 1 << u) // 当前节点怪物活着，尝试击杀
{
int _hp = hp - damage[u][S], _S = S | 1 << u;
if (_hp > 0 && dist < dis[u][_hp][_S])
dis[u][_hp][_S] = dist,
q.push({ u, _hp, _S, dist });
}
for (auto [v, w] : G[u]) // 不管当前节点怪物，先去别的点
if (dist + w < dis[v][hp][S])
dis[v][hp][S] = dist + w,
q.push({ v, hp, S, dist + w });
}
}
int main()
{
cin >> n >> m >> HP;
for (int i = 0; i < n; i++) cin >> d[i];
for (int i = 1, u, v, w; i <= m; i++)
{
cin >> u >> v >> w;
G[u].push_back({ v, w }), G[v].push_back({ u, w });
}
// 预处理
for (int u = 0; u < n; u++)
for (int S = 0; S < 1 << n; S++)
for (Edge e : G[u])
damage[u][S] += !(S & 1 << e.v) * d[e.v];
dijkstra();
int ans = 0x3f3f3f3f;
for (int hp = 0; hp <= HP; hp++)
ans = min(ans, dis[n - 1][hp][(1 << n) - 1]);
cout << (ans == 0x3f3f3f3f ? -1 : ans);
}
```
完结撒花！
蒟蒻一枚，不喜勿喷~~