题面:
现有N个怪物,每个怪物有两个属性\(S_i,K_i\),表示普通攻击和法术攻击杀死该怪物的消耗,同时普通攻击杀死该怪物会产生新的\(R_i\)个怪物,初始只有1号怪物,求使得场上没有怪物的消耗最小
范围&性质:$ 2\le n\le 2\times10^5,1\le \sum R_i\le 10^6,1\le K_i,s_i\le 5\times 10^{14}$
分析:
很容易想到将怪物前后产生关系作为建边的方案,但是因为普通攻击产生的后置影响无法直接计算,所以要在最短路的基础上瞎搞 /bushi
可以推得转移式如下:
\[dis[u]=min(dis[u],dis[v]+s[i]+\sum dis[r[u][i]])
\]
然后我们发现ta很像SPFA的松弛操作,但是对于每一个节点无法保证更新它时他的所有儿子的\(dis[v]\)都已经被更新了,所以每次松弛后要将父亲节点再次入队,等待下一次更新
代码:
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
const int maxn = 1e6+5;
long long n;
long long dis[maxn],s[maxn];
struct edge
{
int to,nxt;
}e[maxn],f[maxn];
int cnt=0,head[maxn];
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int fcnt=0,fhead[maxn];
void fadd(int u,int v)
{
f[++fcnt].to =v;
f[fcnt].nxt=fhead[u];
fhead[u]=fcnt;
}
bool ins[maxn];
void spfa()
{
queue<int> q;
for(int i=1;i<=n;i++) q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
ins[u]=false;
long long tmp=s[u];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
tmp+=dis[v];
}
if(dis[u]>tmp)
{
dis[u]=tmp;
for(int i=fhead[u];i;i=f[i].nxt)
{
int fa=f[i].to;
if(ins[fa]) continue;
q.push(fa);
ins[fa]=true;
}
}
}
}
void work()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
long long tmp,x;
scanf("%lld%lld%lld",&s[i],&dis[i],&tmp);
while(tmp--)
{
scanf("%lld",&x);
add(i,x);
fadd(x,i);
}
}
spfa();
printf("%lld\n",dis[1]);
}
}
int main()
{
zzc::work();
return 0;
}