标签：

「AHOI2014/JSOI2014」骑士游戏

传送门
考虑 \(\text{DP}\)。
设 \(dp_i\) 暗示灭种（雾）一只编号为 \(i\) 的怪物的价钱。
那么转移显然是：
\[dp_i = \min(K_i, S_i + \sum_{j = 1}^{R_i} dp_{v_j})\]
但是我们会发明这个对象是有后效性的。。。
所以我们会想要用建图然后跑一个最短路什么的来搞。。。
于是我们不雅察看到上面阿谁 \(\text{DP}\) 式子中，\(dp_i\) 如果用后面那一项来转移，显然会有 \(dp_{v_j} < dp_i\)。
这提示我们，为了消除后效性，可以对 \(dp\) 值排序。
准确的说就是开一个堆来搞，每个点初始的 \(dp\) 值都是覆灭它的魔法消耗，然后优先更新较小的 \(dp\) 值，
终究我们对付魔法消耗最小的怪物必定是直接覆灭（因为你到头来都要干死它何必生出一些魔法消耗更高的嘞）
然后我们建图方法就是反着来，如果 \(i\) 会生出 \(j\)，那么连边 \(j \to i\)，然后我们就跑一个长的有点像 \(\text{Dijkstra}\) 的 \(\text{DP}\) 就好了。
参考代码：

#include <cstdio> #include <queue> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } typedef long long LL; const int _ = 2e5 + 5, __ = 1e6 + 5; int tot, head[_]; struct Edge { int ver, nxt; } edge[__]; inline void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; } int n, r[_], vis[_]; LL dp[_], s[_], k[_]; struct node { int u; LL val; } ; inline bool operator < (const node& x, const node& y) { return x.val > y.val; } priority_queue < node > Q; int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n); for (rg int i = 1; i <= n; ++i) { read(s[i]), read(k[i]), read(r[i]); for (rg int x, o = 1; o <= r[i]; ++o) read(x), Add_edge(x, i); } for (rg int i = 1; i <= n; ++i) Q.push((node) { i, dp[i] = k[i] }); while (!Q.empty()) { int u = Q.top().u; Q.pop(); if (vis[u]) continue ; vis[u] = 1; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].ver; s[v] += dp[u]; if (dp[v] > s[v] && !--r[v]) dp[v] = s[v], Q.push((node) { v, dp[v] }); } } printf("%lld\n", dp[1]); return 0; }

「AHOI2014/JSOI2014」骑士游戏

，