90分求助
查看原帖
90分求助
428358
Grisses楼主2022/3/4 20:33
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,p[1505],h[1505],dp[1505][3]; 
struct edge{
	int v,nxt;
}e[3005];
bool vis[1505];
void adde(int u,int v){
	e[++cnt].nxt=h[u];
	h[u]=cnt;
	e[cnt].v=v;
}
void dfs(int x,int fa){
	dp[x][0]=p[x];
	int maxn=INT_MAX;
	for(int i=h[x],v;i;i=e[i].nxt){
		if(e[i].v==fa)continue;
		v=e[i].v;
		dfs(v,x);
		dp[x][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
		dp[x][1]+=min(dp[v][2],dp[v][0]);
		maxn=min(maxn,dp[v][0]-min(dp[v][2],dp[v][0]));
		dp[x][2]+=min(dp[v][2],dp[v][0]);
	}
	cerr<<dp[x][2]<<' '<<maxn<<endl;
	dp[x][2]+=maxn;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1,u,k;i<=n;i++){
		scanf("%lld%lld%lld",&u,&p[i],&k);
		for(int j=1,a;j<=k;j++)scanf("%lld",&a),adde(u,a),adde(a,u),vis[a]=1;
	}
	dfs(1,-1);
	printf("%lld",min(dp[1][0],dp[1][2]));
	return 0;
}
2022/3/4 20:33
加载中...