题意

消灭一个魔物有两种方法，消耗\(a_i\)代价将它彻底消灭，或者消耗\(b_i\)代价将它变成多个其他魔物，求消灭1号魔物的最小代价

思路

SPFA：一个点的最短路径被更新后它的儿子节点才可能被更新，于是将该点入队，这样做减少了没有更新的无用枚举

对于这道题，设\(dis_i\)表示一个\(i\)魔物被彻底消灭的代价，（显然最多不超过\(a_i\)），类似上面的思路，不过这里将可能被更新的点入队（而不是上面的被更新过的点），取出队头的一个点，更新它的\(dis\)值，如果更新了就将所有可以转换成它的点全入队就行了；一开始由于不知道从哪个点开始（所有点都可能被更新），选择将所有点入队

Code

#include<bits/stdc++.h>#define N 200005#define Min(x,y) ((x)<(y)?(x):(y))#define Max(x,y) ((x)>(y)?(x):(y))using namespace std;typedef long long ll;int n;ll dis[N],s[N];bool vis[N];struct Edge{ int next,to;}edge[1000005],e[1000005];int head[N],hd[N],cnt=1,ct=1;void add_edge(int from,int to){ edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt;}void add_e(int from,int to){ e[++ct].next=hd[from]; e[ct].to=to; hd[from]=ct;}template <class T>void read(T &x){ char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}void spfa(){ queue<int> q; for(int i=1;i<=n;++i) { q.push(i);vis[i]=1; } while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; ll now=0; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; now+=dis[v]; } if(dis[u]>now+s[u]) { dis[u]=now+s[u]; for(int i=hd[u];i;i=e[i].next) { int v=e[i].to; if(!vis[v]) {q.push(v);vis[v]=1;} } } }}int main(){ read(n); for(int i=1;i<=n;++i) { ll r; read(s[i]);read(dis[i]);read(r); for(int j=1;j<=r;++j) { int x; read(x); add_edge(i,x); add_e(x,i); } } spfa(); cout<<dis[1]<<endl; return 0;}