Luogu

分析

容易想到一个 DP:设 $dp_i$ 表示完全杀死第 $i$ 只怪物的最小花费,容易得到转移

$$ dp_i=\min\left\{k_i,s_i+\sum_{v}dp_v\right\} $$

然而本题中可能存在环,所以这个做法是假的。

既然存在环,那么考虑用最短路来转移。

具体的,一开始令 $dp_i=k_i$,并将所有点入队,然后每次取出队首进行转移。转移时先遍历它的出边,计算得出物理攻击的花费,然后再更新 $dp$ 值。如果更新成功,则所有物理攻击能够打出它的怪物的 $dp$ 值都可能被更新,因此将这些怪物入队。

最后答案即为 $dp_1$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,s[N],k[N];
vector<int> E[N],fE[N];
int ans[N],inq[N];

inline void spfa() { queue<int> Q;
    for (re int i=1;i<=n;++i) ans[i]=k[i],Q.push(i),inq[i]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        int w=s[u];
        for (re int v:E[u]) w+=ans[v];
        if (w<ans[u]) { ans[u]=w;
            for (re int f:fE[u]) if (!inq[f]) Q.push(f),inq[f]=1;
        }
    }
}

signed main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        s[i]=read(),k[i]=read(); int r=read();
        while (r--) { int v=read();
            E[i].push_back(v),fE[v].push_back(i);
        }
    }
    spfa(); printf("%lld\n",ans[1]);
    return 0;
}
最后修改:2020 年 02 月 26 日 08 : 54 AM