RT

代码如下:

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll n,cnt,cnt1;
ll head[200100],head1[200100],vis[200100],dis[200100],val[200100];
struct node{
	ll nxt,to;
}edge[200100],edge1[200100];
void add(ll from,ll to)
{
	edge[++cnt].nxt=head[from];
	edge[cnt].to=to;
	head[from]=cnt;
}
void add1(ll from1,ll to1)
{
	edge1[++cnt1].nxt=head1[from1];
	edge1[cnt1].to=to1;
	head1[from1]=cnt1;
}
void spfa()
{
	queue<ll>q;
	for(ll i=1;i<=n;++i)
	{
		vis[i]=1;
		q.push(i);
	}
	while(!q.empty())
	{
		ll cur=q.front();
		q.pop();
		vis[cur]=0;
		ll mm=val[cur];
		for(ll i=head[cur];i;i=edge[i].nxt)mm+=dis[edge[i].to];
		if(mm>=dis[cur])continue;
		dis[cur]=mm;
		for(ll i=head1[cur];i;i=edge1[i].nxt)
		{
			if(!vis[edge1[i].to])
			{
				vis[edge1[i].to]=1;
				q.push(edge1[i].to);
			}
		}
	}
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i)
	{
		ll x;
		scanf("%lld%lld%lld",&val[i],&dis[i],&x);
		for(ll j=1;j<=x;++j)
		{
			ll m;
			scanf("%lld",&m);
			add(i,m);
			add1(m,i);
		}
	}
	spfa();
	printf("%lld",dis[1]);
	return 0;
}

这里是结果