思路与算法

每类怪物的最优代价不超过法术K。先把所有K作为候选标签入最小堆；普通攻击是S加所有新怪物最优代价之和。建立每个子怪物对父配方的反向出现表，子标签定型后累加一次、未完成数量减一，父配方全部子项定型后才形成新候选。

正确性说明

所有普通攻击S>0，所以一个优于法术的普通攻击方案成本严格大于每一个子项成本。最小未定标签不可能等待一个尚未定型、却能产生更小解的子项；这给出贪心定型的不变式。反向表保留重复怪物，配方和准确，所有有效方案都由法术叶子和正费用配方组成，算法求得最小值。

复杂度

设R=ΣRi≤10^6，读入与初始化O(N+R)，每个反向出现处理一次；每类至多一个普通配方候选，堆O((N+R)logN)时间，空间O(N+R)。

易错点

有循环也不能直接当DAG递归。相同编号多次出生要累计多次。累加截断到当前法术上界≤5×10^14，避免一百万个大代价相加溢出；不影响最小值。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> d(n), sum(n);
    vector<int> rem(n), done(n);
    vector<vector<int>> rev(n);
    for (int i = 0; i < n; i++) {
        cin >> sum[i] >> d[i] >> rem[i];
        sum[i] = min(sum[i], d[i]);
        for (int j = 0; j < rem[i]; j++) {
            int v;
            cin >> v;
            rev[--v].push_back(i);
        }
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    for (int i = 0; i < n; i++)
        q.push({d[i], i});
    while (!q.empty()) {
        auto z = q.top();
        q.pop();
        int u = z.second;
        if (done[u] || d[u] != z.first)
            continue;
        done[u] = 1;
        for (int p : rev[u]) {
            sum[p] = min(d[p], sum[p] + d[u]);
            if (!--rem[p] && !done[p] && sum[p] < d[p]) {
                d[p] = sum[p];
                q.push({d[p], p});
            }
        }
    }
    cout << d[0] << '\n';
}