思博贪心题写了一个半小时没救了，我也没看出这是一个(spfa)来啊
设(dp_i)表示彻底干掉第(i)只怪物的最小花费，一个非常显然的事情，就是对于(k_i)值最小的怪物满足(dp_i=k_i)
非常好理解，反正到最后都要干掉这个怪物，何必再把它干成别的怪物
于是我们按照(k_i)的值先排序一下，另外维护一个小根堆
如果堆里没有点或者堆顶的(dp)值比当前的(k)要大，我们直接令当前当前(k_i)值最小的点(i)的(dp_i=k_i)，之后遍历所有能到达点(i)的点(v)，令(s_v+=dp_i)，如果发现点(v)的所有出边都被遍历了一遍，我们就令(dp_v=min(s_v,k_v))，同时把这个点加入堆中
如果堆里有点且堆顶的(dp)小于于当前(k)，就直接拿堆顶来更新
考虑这个做法的正确性，显然当前堆中没有节点的时候，图中任意一个点不可能只分解成已经处理好(dp_i)的点，于是我们必须引入剩下的(k)值最小的点
或者把堆中没有点的情况视为初始情况，可能这样更好理解
代码
#include <bits/stdc++.h>
#define re register
#define LL long long
#define mp std::make_pair
#define min(a, b) ((a) < (b) ? (a) : (b))
const int maxn = 2e5 + 5;
struct E {
int v, nxt;
} e[1000005];
LL dp[maxn], s[maxn], w[maxn];
int head[maxn], vis[maxn], c[maxn], p[maxn];
int n, num, top;
inline LL read() {
LL x = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = (x << 3ll) + (x << 1ll) + c - 48, c = getchar();
return x;
}
typedef std::pair<LL, int> pii;
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > q;
inline int cmp(int a, int b) { return s[a] < s[b]; }
inline void del(int x) {
vis[x] = 1;
for (re int i = head[x]; i; i = e[i].nxt) {
if (vis[e[i].v])
continue;
w[e[i].v] += dp[x];
c[e[i].v]--;
if (!c[e[i].v])
vis[e[i].v] = 1, dp[e[i].v] = min(w[e[i].v], s[e[i].v]), q.push(mp(dp[e[i].v], e[i].v));
}
}
inline void add(int x, int y) {
e[++num].v = y;
e[num].nxt = head[x];
head[x] = num;
}
int main() {
n = read();
for (re int x, i = 1; i <= n; i++) {
w[i] = read(), s[i] = read(), c[i] = read();
for (re int j = 1; j <= c[i]; j++) x = read(), add(x, i);
}
for (re int i = 1; i <= n; i++) p[i] = i;
std::sort(p + 1, p + n + 1, cmp);
int now = 1, tot = 0;
while (tot < n) {
while (vis[p[now]]) ++now;
if (!q.empty() && (q.top().first < s[p[now]] || now > n))
tot++, del(q.top().second), q.pop();
else
tot++, dp[p[now]] = s[p[now]], del(p[now++]);
}
printf("%lld
", dp[1]);
return 0;
}