「AHOI&JSOI 2014」骑士游戏

题目大意：

设杀死怪物 $i$ 的最小代价为 $f[i]$，有

$$f[i]=\min(k_i,s_i+\sum\limits f[j])$$

$j$ 为 $i$ 被普通攻击后分裂出的怪物。

考虑 $k_i$ 最小的点，这个怪兽肯定是被法术杀死的，它的 $f$ 值是确定的，于是只能变成这个怪兽的怪兽就可以转移了。这就很像拓扑序时的操作，每次选一个 $k_i$ 最小的点，更新 $f$ 值，如果某个点能变成所有的怪兽都被更新过了，那就更新这个怪兽，否则再重复这个过程直到所有怪兽都被更新完。

#include <cstdio>
#include <queue>
 
typedef long long LL;
const int N = 200005, M = 1000005;
struct Pair {
    LL x; int y;
    bool operator < (const Pair &rhs) const {
        return x > rhs.x;
    }
};
int vis[N], d[N], head[N], nxt[M], v[M], tot, n; LL k[N], s[N], t[N];
std::priority_queue<Pair> Q;
 
LL read() {
    LL x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void adde(int from, int to) {
    nxt[++tot] = head[from];
    head[from] = tot, v[tot] = to;
}
void dijkstra() {
    while (!Q.empty()) {
        int u = Q.top().y; Q.pop();
        if (vis[u]) continue;
        if (u == 1) return;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i]) {
            t[v[i]] += k[u];
            if (--d[v[i]] == 0) {
                if (k[v[i]] > t[v[i]] + s[v[i]])
                    k[v[i]] = t[v[i]] + s[v[i]];
                Q.push((Pair){k[v[i]], v[i]});
            }
        }
    }
}
 
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        s[i] = read(), k[i] = read(), d[i] = read();
        for (int j = 1; j <= d[i]; ++j) adde(read(), i);
        Q.push((Pair){k[i], i});
    }
    dijkstra();
    printf("%lld\n", k[1]);
    return 0;
}