POJ 1935 Journey G++ 博友两个思路实现其一 dfs巧妙没掌握

xiaoxiao2021-02-28  99

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <utility> using namespace std; //英语 看博友好分析 抄博友程序 博友两个思路实现其一 dfs 巧妙 没掌握 vector<pair<int,int> > g[100010];//抄博友程序 int dis[100010]; int vis[100010]; int res; void dfs(int u,int pre) { for(int i=0;i<g[u].size();i++) { int v=g[u][i].first; if(v==pre) { continue;//抄博友程序 } dis[v]=dis[u]+g[u][i].second;//抄博友程序 dfs(v,u); if(vis[v])//抄博友分析 传递标记 没掌握 { vis[u]=true; res+=g[u][i].second*2; } } } int main() { int n,root; //cin>>n>>root; scanf("%d%d",&n,&root); for(int i=1;i<n;i++) { int x,y,z; //cin>>x>>y>>z; scanf("%d%d%d",&x,&y,&z); g[x].push_back(pair<int,int> (y,z)); g[y].push_back(pair<int,int> (x,z)); } int m; cin>>m; for(int i=1;i<=m;i++) { int x; //cin>>x; scanf("%d",&x); vis[x]=true;//抄博友分析 打上标记 } dfs(root,0); int mx=0; for(int i=1;i<=n;i++) { if(vis[i]) { mx=max(mx,dis[i]); } } cout<<res-mx<<endl; return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-60180.html

最新回复(0)