A22711

题目分析
1.两种选择：法术攻击：直接花费 $K_i$ 杀死怪兽 $i$，代价确定。普通攻击：花费 $S_i$ 杀死怪兽 $i$，但会产生一堆新怪兽 $\{L_1, L_2, \dots, L_{R_i}\}$。要彻底杀死怪兽 $i$，你必须再把这些新产生的怪兽全部杀掉。
2.核心矛盾：怪兽之间可能存在环形依赖。例如：杀死 A 产生 B，杀死 B 产生 A。这导致我们不能简单地用树形 DP 或记忆化搜索来解决，因为搜索会进入死循环。
3.抽象模型：设 $dp[i]$ 为杀死怪兽 $i$ 的最小体力消耗。状态转移方程为：dp[i] = \min(K_i, S_i + \sum_{j \in Next_i} dp[j])由于存在环，这个方程类似于最短路中的 $dist[u] = \min(dist[u], dist[v] + w)$。

解题思路：SPFA 思想
我们可以把每种怪兽看作图中的一个点。初始时，令 $dp[i] = K_i$（即全部用法术攻击）。然后尝试利用普通攻击来更新：如果 $S_i + \sum dp[next]$ 比当前的 $dp[i]$ 更小，就更新 $dp[i]$。关键点：当某个 $dp[j]$ 减小时，所有“普通攻击后会产生怪兽 $j$”的怪兽 $i$ 的总代价都有可能随之减小。因此，我们需要建立反向图：从产生的怪兽指向母体怪兽。算法流程建图：正向记录：每个怪兽普通攻击后产生的怪兽列表（用于计算 $\sum dp$）。反向建图：如果 $i$ 普通攻击产生 $j$，则建一条 $j \to i$ 的边（用于更新触发）。初始化：$dp[i] = K_i$。$sum[i] = S_i + \sum K_{next}$（初始假设所有后继都用法术）。迭代更新：使用类似 SPFA 的队列，将所有点入队。不断出队点 $u$，检查其 $dp[u]$ 是否能优化其反向边指向的母体怪兽 $v$。如果 $S_v + \sum dp_{new} < dp[v]$，更新 $dp[v]$ 并将 $v$ 再次入队。
代码实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 使用 long long 防止体力值溢出
typedef long long ll;

const int MAXN = 200005;
ll S[MAXN], K[MAXN], dp[MAXN], sum_dp[MAXN];
vector<int> forward_adj[MAXN]; // 正向：i 产生哪些怪兽
vector<int> backward_adj[MAXN]; // 反向：哪些怪兽产生 i
bool in_que[MAXN];

void solve() {
    int n;
    if (!(cin >> n)) return;

    for (int i = 1; i <= n; ++i) {
        int r;
        cin >> S[i] >> K[i] >> r;
        dp[i] = K[i]; // 初始代价设定为法术攻击
        for (int j = 0; j < r; ++j) {
            int target;
            cin >> target;
            forward_adj[i].push_back(target);
            backward_adj[target].push_back(i); // 反向建边
        }
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        ll current_sum = S[i];
        for (int next_m : forward_adj[i]) {
            current_sum += dp[next_m];
        }
        sum_dp[i] = current_sum;
        
        // 初始全部入队进行松弛操作
        q.push(i);
        in_que[i] = true;
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_que[u] = false;

        // 如果发现 (普通攻击代价 + 后继怪兽总代价) 更优
        if (sum_dp[u] < dp[u]) {
            ll diff = dp[u] - sum_dp[u];
            dp[u] = sum_dp[u];

            // 既然 dp[u] 变小了，所有产生 u 的母体怪兽的 sum_dp 都要减小
            for (int v : backward_adj[u]) {
                sum_dp[v] -= diff;
                if (!in_que[v]) {
                    q.push(v);
                    in_que[v] = true;
                }
            }
        }
    }

    cout << dp[1] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

代码要点
1.sum_dp 的维护：我们不应该每次都遍历 forward_adj 去重新计算总和，那样复杂度会退化。通过计算 diff = old_dp - new_dp，直接在母体的 sum_dp 中减去差值，效率最高。
2.入队时机：只要母体怪兽 $v$ 的 sum_dp 减小了，它就有可能使得 $v$ 的 dp[v] 进一步减小，所以必须入队检查。
复杂度：类似于 SPFA，在处理此类有向图最优值更新时效果很好。虽然最坏情况下 SPFA 复杂度较高，但在此类 DP 转移问题中通常能稳定通过