[AHOI2014/JSOI2014]骑士游戏
杀死魔物有两种方式 魔法或者物理攻击再让它去世
则 dis = min(魔法 ， 物理 所有子代魔法);
就像dp，然而可能成环。考虑spfa成环距离必定大于最小距离（边为正数）。
一般spfa需要知道起点，这里不知道从哪里开始有最优解，就把所有点都加进去（貌似入度为零加了会更快？）
也不知道终点，则每次松弛成功就把它能影响到的结点再次入队。
代码语言：javascript复制//深入理解spfa
#include <bits/stdc .h>
using namespace std;
#define ll long long
const int N = 250000;
ll dis[N],a[N];
vector<ll> from[N],to[N];
int book[N];
int n;
ll read(){
ll x=0,sign=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10 c-'0';
c=getchar();
}
return x*sign;
}
void spfa(){
queue<int> q;
for(int i=1;i<=n;i )book[i]=1,q.push(i);//不知道从哪开始为最优解
while(!q.empty()){
int u = q.front(); book[u] = 0; q.pop();
ll temp = a[u];
for(int i=0;i<from[u].size();i )temp =dis[from[u][i]];
if(dis[u]<=temp)continue;
dis[u] = temp;
for(int i=0;i<to[u].size();i ){//松弛成功 可以影响到的点重新入队
if(!book[to[u][i]]){
q.push(to[u][i]);
book[to[u][i]]=1;
}
}
}
}
int main()
{
n = read();
for(int i=1;i<=n;i ){
int r,u,v;
a[i] = read(); dis[i] = read(); r=read(); //初始化dis为魔法值
while(r--){
v = read();
from[i].push_back(v);//i 可以到达v
to[v].push_back(i);//v可以影响到i
}
}
spfa();
printf("%lld",dis[1]);
return 0;
} 
