骑士游戏（spfa好题）

P4042 [AHOI2014/JSOI2014]骑士游戏

分析：
spfa好题
很明显的转移是：f[u]=min(法术,sigma(f[v]))
显然要将一个怪兽产生另一个的关系连边
但是问题在于f有后效性，当前的f[u]更新了，可能还会对之前会产生u的其它点有影响
而spfa就可以解决这个问题。
将转移式子看作是松弛操作，每一次如果u可以被更新，说明连向u的点都应该又被更新一遍
所以将原图建反图，对连向u的点再次入队，等待被更新

#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define N 200005
#define ll long long
bool vis[N];
int n;
ll dis[N],a[N];
vector<int> e1[N];
vector<int> e2[N];
void spfa()
{
    queue<int> q;
    for(ri i=1;i<=n;++i) q.push(i),vis[i]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=0;// printf("u:%d
",u);
        ll tmp=a[u];
        for(ri i=0;i<e1[u].size();++i) tmp+=dis[e1[u][i]];
        if(tmp>=dis[u]) continue;
        dis[u]=tmp;
        for(ri i=0;i<e2[u].size();++i){
            int v=e2[u][i];
            if(!vis[v]) q.push(v),vis[v]=1;
        }
    }
    printf("%lld
",dis[1]);
}
int main()
{
    scanf("%d",&n);
    int x,xx;
    for(ri i=1;i<=n;++i){
        scanf("%lld%lld%d",&a[i],&dis[i],&x);
        while(x--){
            scanf("%d",&xx);
            e1[i].push_back(xx); e2[xx].push_back(i);
        }
    }
    spfa();
    return 0;
}