BZOJ3875: [Ahoi2014&Jsoi2014]骑士游戏

【传送门：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[];

vector<int>cd[];

bool v[];

LL f[],s[],k[];

int main()

{

    int n;

    scanf("%d",&n);

    int head=,tail=;int r;

    for(int i=;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()==)

    {

        int x=q.front();

        LL d=s[x];

        for(int i=;i<c[x].size();i++) d+=f[c[x][i]];

        if(f[x]>d)

        {

            f[x]=d;

            for(int i=;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[]);

    return ;

}