【传送门：BZOJ3875】
简要题意：
给出n种怪物，每种怪物都带有三个值，S[i]，K[i]，R[i]，分别表示对他使用普通攻击的花费，使用魔法攻击的花费，对他使用普通攻击后生成的其他怪物。
每种怪物只能用法术攻击来消灭，用普通攻击只能将怪物变成其他怪物
当前第一种怪物来了，请问将怪物完全消灭的最小花费
题解：
首先一看就像DP，设f[i]为消灭第i种怪物的最小花费，可以列出方程：f[i]=min(K[i],∑f[j](将第i种怪物能生成的怪物消灭的最小花费总和))
但是这种方法显然会出现环，那么我们就用近似SPFA的方法来解决这个问题
首先将每种怪物放入队列，然后设d=s[x]+∑f[j]，如果d<f[x]的话，就更新f[x]
但是我们不但要更新f[x]，还要更新能够生成第x种怪物的怪物，所以我们就要把这些怪物也放进队列里（如果这些怪物本身就在队列里的话，就不用）
最后输出f[1]就可以了
PS：要用STL容器来保存怪物生成怪物的信息（不然会爆空间），而且最好用queue来保存队列
参考代码：
#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<vector>#include<queue>using namespace std;typedef long long LL;queue<int>q;vector<int>c[210000];vector<int>cd[210000];bool v[210000];LL f[210000],s[210000],k[210000];int main(){ ???int n; ???scanf("%d",&n); ???int head=1,tail=1;int r; ???for(int i=1;i<=n;i++) ???{ ???????scanf("%lld%lld",&s[i],&k[i]); ???????f[i]=k[i]; ???????scanf("%d",&r); ???????q.push(i);v[i]=true; ???????while(r--) ???????{ ???????????int x; ???????????scanf("%d",&x); ???????????c[i].push_back(x); ???????????cd[x].push_back(i); ???????} ???} ???while(q.empty()==0) ???{ ???????int x=q.front(); ???????LL d=s[x]; ???????for(int i=0;i<c[x].size();i++) d+=f[c[x][i]]; ???????if(f[x]>d) ???????{ ???????????f[x]=d; ????????????for(int i=0;i<cd[x].size();i++) ???????????{ ???????????????if(v[cd[x][i]]==false) ???????????????{ ???????????????????v[cd[x][i]]=true; ???????????????????q.push(cd[x][i]); ???????????????} ???????????} ???????} ???????q.pop(); ???????v[x]=false; ???} ???printf("%lld\n",f[1]); ???return 0;}BZOJ3875: [Ahoi2014&Jsoi2014]骑士游戏
原文地址：http://www.cnblogs.com/Never-mind/p/7909516.html