自动搬运

查看原文

来自洛谷，原作者为

	a_cow_of_FJ 奶龙的传人

搬运于2025-08-24 22:57:49，当前版本为作者最后更新于2025-07-28 10:48:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题思路十分暴力：拆点 + 状态压缩 + dijkstra

估计是最慢的一篇题解了。

题意

$n$ 个点 $m$ 条边的带权无向图，点从 $0$ ~ $n-1$ 编号。初始时每个点上都有一个怪物，不同怪物有不同攻击力。你从 $0$ 号点出发，在一个点上可以击杀该节点上的怪物，虽然不花时间但是会受到相邻的存活的怪物的攻击。问最快什么时候击杀所有怪物并且到达点 $n-1$。

注意：

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，答案即为：

还有一点，就是不同击杀状态下击杀每个点的怪物所受到的伤害可以预处理出来（$damage[u][S]$ 表示击杀状态为 $S$ 下击杀点 $u$ 所受伤害，前提得保证击杀前 $u$ 还活着）：

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)$，但实际上远没有那么高。

代码

#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);
}

完结撒花！

蒟蒻一枚，不喜勿喷~~