Description
在这个游戏中，JYY 一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统 bug，并不保证这一点）。
游戏世界中一共有 \(N\) 种不同的怪兽，分别由 \(1\) 到 \(N\) 编号，现在 \(1\) 号怪兽入侵村庄了，JYY 想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？
Solution
设 \(atk_i,atr_i\) 分别表示普通攻击和法术攻击的代价，普通攻击产生的怪兽记为被攻击怪兽的儿子。
很容易得到一个 DP。设 \(f_x\) 表示杀死怪兽 \(x\) 的最小代价。那么有 \(f_x=\min\{atr_i,atk_i+\sum_{y\in son} f_y\}\)。
但是这个 DP 是存在后效性的。因此我们考虑建图，用最短路解决这个问题。
但这并不是普通的最短路。以 SPFA 为例，SPFA 队列中的点是被更新的，因此它有更新别的点的可能。换句话说，是父亲更新儿子。但是这道题，是儿子来更新父亲，所以队列中的点不再是被更新过的，而是可能能被更新的点。对于队列中的的一个点，枚举它的儿子，得到它的儿子 \(\sum f\)，然后判断能否更新。如果能够更新，就把它的父亲拉入队列，因为此时它的父亲也有可能能被更新。
初始化时，\(f_i=atr_i\)，并且所有点入队列，因为所有点在一开始的时候都可能能被更新。
Code
#include<queue>
#include<cstdio>
#include<cstring>
#define N 200005
#define R 1000005
#define ll long long
using namespace std;
int n,tot,_tot;
ll atk[N],atr[N],dis[N];
bool bj[N];
struct node {int to,next,head;}a[R],_a[R];
queue<int> q;
void add(int x,int y) {a[++tot].to=y;a[tot].next=a[x].head;a[x].head=tot;}
void _add(int x,int y) {_a[++_tot].to=y;_a[_tot].next=_a[x].head;_a[x].head=_tot;}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
int num;
scanf("%lld%lld%d",&atk[i],&atr[i],&num);
while (num--)
{
int x;
scanf("%d",&x);
add(i,x);_add(x,i);
}
}
for (int i=1;i<=n;++i)
q.push(i),dis[i]=atr[i];
memset(bj,true,sizeof(bj));
while (!q.empty())
{
int x=q.front();q.pop();
bj[x]=false;
ll res=atk[x];
for (int i=a[x].head;i;i=a[i].next)
res+=dis[a[i].to];
if (res<dis[x])
{
dis[x]=res;
for (int i=_a[x].head;i;i=_a[i].next)
if (!bj[_a[i].to]) bj[_a[i].to]=true,q.push(_a[i].to);
}
}
printf("%lld\n",dis[1]);
return 0;
}