题目传送门:BMOJ P110722Luogu P4042

Description

在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统bug,并不保证这一点)。

游戏世界中一共有N种不同的怪兽,分别由1到N编号,现在1号怪兽入侵村庄了,JYY想知道,最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢?

Solution

$$f[i]=\min (K_i,S_i+\sum_{\text{怪兽}i\text{死亡会产生怪兽}j} f[j])$$

因为可能会有环出现,所以用SPFA优化DP。

$f[i]$ 初始值应该设为 $K[i]$ 。注意假如 $S_i+\sum f[j]$ 能更新,就要把 $i$ 的父节点加入队尾,所以要建双向边。

Code

/*
 * @Name: 110722
 * @Author: Lovely_XianShen
 * @Date: 2019-10-29 16:14:58
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}
typedef long long ll;
const int N = 200005;

int n, m;
bool vis[N];
ll f[N], dp[N];
int cnt1, cnt2, head1[N], head2[N];

struct edg {
    int to, nxt;
} e1[N * 5], e2[N * 5];

inline void add(int x, int y) {
    e1[ ++cnt1 ].to = y;
    e1[ cnt1 ].nxt = head1[ x ];
    head1[ x ] = cnt1;
    e2[ ++cnt2 ].to = x;
    e2[ cnt2 ].nxt = head2[ y ];
    head2[y] = cnt2;
}

queue<int> q;

inline void spfa() {
    for (int i = 1; i <= n; i++)
        q.push(i), vis[i] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        ll tmp = f[x];
        for (int i = head1[x]; i; i = e1[i].nxt)
            tmp += dp[e1[i].to];
        if (tmp < dp[x]) {
            dp[x] = tmp;
            for ( int i = head2[ x ]; i ; i = e2[ i ].nxt )
                if ( !vis[ e2[ i ].to ] )
                    vis[ e2[ i ].to ] = 1, q.push( e2[ i ].to );
        }
    }
}

int main() {
    scanf( "%d", &n );
    for ( int i = 1 ; i <= n ; i++ ) {
        int x;
        scanf( "%lld%lld%d", &f[ i ], &dp[ i ], &x );
        while ( x-- ) {
            int y;
            scanf( "%d", &y );
            add( i, y );
        }
    }
    spfa();
    return printf("%lld\n", dp[1]), 0;
}