BZOJ-3875: [Ahoi2014&Jsoi2014]骑士游戏

Description

JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。游戏世界中一共有N种不同的怪兽，分别由1到N编号，现在1号怪兽入侵村庄了，JYY想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？2<=N<=2*10^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=5*10^14

有种解法是spfa，将法术攻击每个怪兽的体力值当做初始的路径长度，之后优化一个dis之后，将其推进队列，再更新其他怪兽。
考场（Pan出的）上看到这道题的时候不得不说把spfa给直接pas了。感觉会重复更新啊。。。时间复杂度很迷啊。。好吧，我承认我在口胡。
我的做法好像是贪心？？？
如果按照打死每种怪兽的最小体力给怪兽排序的话，可知，假如一个耗体力大的怪兽是被普通攻击了，那么其变成的怪兽一定排在它前面（体力值比他小）。换言之，按照所耗体力值从小到大枚举每个怪兽，由当前枚举过的怪兽更新没有被枚举怪兽的体力值，再找到没有被枚举的怪兽中体力值最小的怪兽继续枚举，枚举的顺序一定是按照打死每种怪兽的最小体力递增排序的，当前体力值也是最小体力值。
可以拿堆维护这个过程，每次拿出堆顶，更新刚好达到条件的点（条件即为该点所有出边指向的点都已出堆），如果更优则推入堆中，重复这个过程。
发现暴力判断条件的话时间复杂度显然不对，我们可以用拓扑的思想，建一张反图，每出堆一个点就将其连向的点入度-1，直至入度为0的时候更新该点。
时间复杂度O(nlogn+m)
你告诉我这是dij？？？。。。好像挺像的
像你个头啊！！！

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dis[200200],p[200200];
int n,rd[200200];
vector<int>v[200200],v1[200200];
bool vis[200200];
void read(int &x)
{
    x=0; int f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f;
}
void read_ll(ll &x)
{
    x=0; int f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f;
}
struct node
{
    int v;ll dis;
};
bool operator < (node x,node y) {return x.dis>y.dis;}
priority_queue<node>he;
int main()
{
    read(n); int x,y;
    for(int i=1;i<=n;++i)
    {
        read_ll(p[i]); read_ll(dis[i]); read(rd[i]);
        for(int j=1;j<=rd[i];++j)
        {
            read(x); v[x].push_back(i);
            v1[i].push_back(x);
        }
        if(!rd[i]) dis[i]=min(dis[i],p[i]);
    }
    for(int i=1;i<=n;++i) he.push((node){i,dis[i]});
    for(int i=1;i<=n;++i)
    {
        while(!he.empty())
        {
            x=he.top().v; he.pop();
            if(vis[x]) continue; else break;
        }
        vis[x]=1;
        for(int j=0;j!=v[x].size();++j)
        {
            y=v[x][j]; rd[y]--;
            if(!rd[y]&&!vis[y])
            {
                ll tmp=p[y];
                for(int k=0;k!=v1[y].size();++k) tmp+=dis[v1[y][k]];
                if(tmp<dis[y]) dis[y]=tmp,he.push((node){y,dis[y]});
            }
        }
    }
    printf("%lld",dis[1]);
    return 0;
}