AC,但样例输出20
查看原帖
AC,但样例输出20
479066
MrJXS楼主2023/12/31 14:25
#include<bits/stdc++.h>
using namespace std;
vector<int> son[1505];
int n,dp[1505][3],arr[1505],fa[1505],root; //0£º±»×Ô¼º¸²¸Ç   1£º±»¸¸½Úµã¸²¸Ç    2£º±»×ӽڵ㸲¸Ç 
void dfs(int u){
	dp[u][0]=arr[u];
	bool flag=1;
	int minn=2147483647;
	for(int i=0;i<son[u].size();i++){
		int v=son[u][i];
		dfs(v);
		dp[u][0]=dp[u][0]+min(dp[v][0],min(dp[v][1],dp[v][2]));
		dp[u][1]=dp[u][1]+min(dp[v][0],dp[v][2]);
		if(dp[v][2]<dp[v][0]){
			dp[u][2]+=dp[v][2];
		}else{
			dp[u][2]+=dp[v][0];
			flag=0;
		}
		minn=min(minn,dp[v][0]-dp[v][2]);
	}
	if(flag){
		dp[u][2]+=minn;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,temp;
		cin>>a>>arr[a]>>temp;
		for(int j=1,t;j<=temp;j++){
			cin>>t;
			son[a].push_back(t);
			fa[t]=a;
		}
	}
	for(int i=1;i<=n;i++){
		if(fa[i]==0) root=i;
	}
	dfs(root);
	cout<<min(dp[root][0],dp[root][2]);
	return 0;
}
2023/12/31 14:25
加载中...