3 条题解
-
10
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; int dp[N][3],n,u,v,n1; vector<int>vc[N]; void dfs(int u,int fa){ bool flag=0; int minn=INF; for(int i=0;i<vc[u].size();i++){ int v=vc[u][i]; if(v==fa)continue; dfs(v,u); dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2])); dp[u][2]+=min(dp[v][0],dp[v][1]); dp[u][1]+=min(dp[v][0],dp[v][1]); minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1])); } dp[u][1]+=minn; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>u; cin>>dp[u][0]; cin>>n1; for(int j=1;j<=n1;j++){ cin>>v; vc[u].push_back(v); vc[v].push_back(u); } } dfs(1,0); cout<<min(dp[1][0],dp[1][1]); }
信息
- ID
- 474
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 151
- 已通过
- 43
- 上传者