传送门
题意简述:nnn个怪物,对于编号为iii的怪物可以选择用aia_iai代价将其分裂成另外的bib_ibi个怪物或者用cic_ici代价直接消灭它,现在问消灭编号为1的怪物用的最小代价。
思路:考虑dpdpdp,消灭iii号怪物的代价fi=min{ci,ai∑fv},v指分裂的怪物f_i=min\{c_i,a_i\sum f_v\},v指分裂的怪物fi=min{ci,ai∑fv},v指分裂的怪物
然后这个东西可能有后效性,考虑如何处理后效在这里插入代码片
性。
发现可以用分裂关系来建立有向图来dpdpdp,每个怪物的代价相当于只跟后继的代价有关,这样可以用spfaspfaspfa来维护dpdpdp,由于一旦一个怪物被更新会影响到所有能分裂出它的怪物,因此我们同时建立一个反图,一旦一个怪物被更新就把反图的后继加进队列。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=2e5+5;
ll dist[N],s[N];
int q[N*20],hd,tl,n;
bool in[N];
vector<int>e[N],g[N];
inline void spfa(){
hd=1,tl=0;
for(ri i=1;i<=n;++i)in[q[++tl]=i]=1;
while(hd<=tl){
int x=q[hd++];
in[x]=0;
ll tmp=s[x];
for(ri i=0;i<e[x].size();++i)tmp+=dist[e[x][i]];
if(tmp>=dist[x])continue;
dist[x]=tmp;
for(ri i=0;i<g[x].size();++i)if(!in[g[x][i]])in[q[++tl]=g[x][i]]=1;
}
}
int main(){
n=read();
for(ri i=1,k,v;i<=n;++i){
s[i]=read(),dist[i]=read();
k=read();
while(k--)v=read(),e[i].push_back(v),g[v].push_back(i);
}
spfa();
cout<<dist[1];
return 0;
}