Link
直接转移可能会有环对吧，所以用spfa转移就完事了。

#include <bits/stdc++.h> #define LL long long using namespace std; namespace IO { char ibuf[(1<<21)+1],*iS,*iT; char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); } LL read() { LL x=0; char ch=Get(); while(ch>'9'||ch<'0') ch=Get(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=Get(); return x; } } using namespace IO; int max(int a,int b){return a>b? a:b;} const int N=4e5+7; vector<int>from[N],ver[N]; queue<int>q; LL a[N],d[N]; int vis[N]; int main() { int n=read(),i,num,x; LL tmp; for(i=1;i<=n;++i) { a[i]=read(),d[i]=read(),num=read(); while(num) x=read(),from[i].push_back(x),ver[x].push_back(i),--num; } for(int i=1;i<=n;++i) q.push(i),vis[i]=1; while(!q.empty()) { x=q.front(),q.pop(),vis[x]=0,tmp=a[x]; for(i=0;i<from[x].size();++i) tmp+=d[from[x][i]]; if(tmp<d[x]) { d[x]=tmp; for(i=0;i<ver[x].size();++i) if(!vis[num=ver[x][i]]) vis[num]=1,q.push(num); } } return cout<<d[1],0; }

Luogu P4042 [AHOI2014/JSOI2014]骑士游戏

，