luogu 4042 有后效性的dp

存在有后效性的dp，但转移方程

f[i] = min( f[i], s[i] + sigma f[j] ( j 是后效点) )

每次建当前点和 转移点的边 e1, 某点和其会影响的点 e2

spfa 利用以前的转移点更新答案，然后将所有受到其影响的点放入队列中再次更新

spfa 处理有后效性的dp

#include<bits/stdc++.h>

#define int long long

#define rep(i,x,y) for(register int i=x;i<=y;i++)

using namespace std;

const int N=2e5+;

const int M=1e6+;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

int head1[N],tot1,head2[N],tot2,n,f[N],s[N];

struct node{int v,next;}e[M],e2[M];

inline void insert1(int u,int v){

    e[++tot1]=(node){v,head1[u]};head1[u]=tot1;}

inline void insert2(int u,int v){

    e2[++tot2]=(node){v,head2[u]};head2[u]=tot2;}

bool vis[N];

queue<int> q;

inline void spfa(){

    rep(i,,n) q.push(i),vis[i]=;

    while(!q.empty()){

        int u=q.front();q.pop();vis[u]=;

        int sum=;

        for(int i=head1[u];i;i=e[i].next){

            int v=e[i].v;

            sum+=f[v];

        }

        sum+=s[u];

        if(sum<f[u]){

            f[u]=sum;

            for(int i=head2[u];i;i=e2[i].next){

                int v=e2[i].v;

                if(!vis[v]){

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

}

#undef int

int main(){

#define int long long

    n=read();

    rep(i,,n){

        s[i]=read(),f[i]=read();int k=read();

        rep(j,,k){

            int r=read();

            insert1(i,r);insert2(r,i);

        }

    }

    spfa();

    printf("%lld\n",f[]);return ;

}