题目分析 1.两种选择：法术攻击：直接花费 KiK_iKi 杀死怪兽 iii，代价确定。普通攻击：花费 SiS_iSi 杀死怪兽 iii，但会产生一堆新怪兽 {L1,L2,…,LRi}\{L_1, L_2, \dots, L_{R_i}\}{L1 ,L2 ,…,LRi }。要彻底杀死怪兽 iii，你必须再把这些新产生的怪兽全部杀掉。 2.核心矛盾：怪兽之间可能存在环形依赖。例如：杀死 A 产生 B，杀死 B 产生 A。这导致我们不能简单地用树形 DP 或记忆化搜索来解决，因为搜索会进入死循环。 3.抽象模型：设 dp[i]dp[i]dp[i] 为杀死怪兽 iii 的最小体力消耗。状态转移方程为：dp[i] = \min(K_i, S_i + \sum_{j \in Next_i} dp[j])由于存在环，这个方程类似于最短路中的 dist[u]=min⁡(dist[u],dist[v]+w)dist[u] = \min(dist[u], dist[v] + w)dist[u]=min(dist[u],dist[v]+w)。 解题思路：SPFA 思想 我们可以把每种怪兽看作图中的一个点。初始时，令 dp[i]=Kidp[i] = K_idp[i]=Ki （即全部用法术攻击）。然后尝试利用普通攻击来更新：如果 Si+∑dp[next]S_i + \sum dp[next]Si +∑dp[next] 比当前的 dp[i]dp[i]dp[i] 更小，就更新 dp[i]dp[i]dp[i]。关键点：当某个 dp[j]dp[j]dp[j] 减小时，所有“普通攻击后会产生怪兽 jjj”的怪兽 iii 的总代价都有可能随之减小。因此，我们需要建立反向图：从产生的怪兽指向母体怪兽。算法流程建图：正向记录：每个怪兽普通攻击后产生的怪兽列表（用于计算 ∑dp\sum dp∑dp）。反向建图：如果 iii 普通攻击产生 jjj，则建一条 j→ij \to ij→i 的边（用于更新触发）。初始化：dp[i]=Kidp[i] = K_idp[i]=Ki 。sum[i]=Si+∑Knextsum[i] = S_i + \sum K_{next}sum[i]=Si +∑Knext （初始假设所有后继都用法术）。迭代更新：使用类似 SPFA 的队列，将所有点入队。不断出队点 uuu，检查其 dp[u]dp[u]dp[u] 是否能优化其反向边指向的母体怪兽 vvv。如果 Sv+∑dpnew<dp[v]S_v + \sum dp_{new} < dp[v]Sv +∑dpnew <dp[v]，更新 dp[v]dp[v]dp[v] 并将 vvv 再次入队。 代码实现 代码要点 1.sum_dp 的维护：我们不应该每次都遍历 forward_adj 去重新计算总和，那样复杂度会退化。通过计算 diff = old_dp - new_dp，直接在母体的 sum_dp 中减去差值，效率最高。 2.入队时机：只要母体怪兽 vvv 的 sum_dp 减小了，它就有可能使得 vvv 的 dp[v] 进一步减小，所以必须入队检查。 复杂度：类似于 SPFA，在处理此类有向图最优值更新时效果很好。虽然最坏情况下 SPFA 复杂度较高，但在此类 DP 转移问题中通常能稳定通过