链接:https://www.nowcoder.com/acm/contest/188/C
来源:牛客网
第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路
一个数表示答案
(我居然连这种题都不会了啊,太笨了!!! 加油啊.....(miss mt) )
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=50007; struct node { int nxt; LL len; }; vector < vector <node> > g(N); LL dis[N]; int n,x; LL mmax; void dfs (int rt,int fa) { for (int i=0;i<g[rt].size();i++) { int nxt=g[rt][i].nxt; int len=g[rt][i].len; if (nxt!=fa) { dis[nxt]=dis[rt]+len; mmax=max (mmax,dis[nxt]); dfs (nxt,rt); } } return ; } int main () { scanf ("%d %d",&n,&x); LL ans=0; dis[x]=0; for (int i=1;i<n;i++) { int u,v; LL w; scanf ("%d %d %lld",&u,&v,&w); node tmp={v,w}; g[u].push_back(tmp); tmp.nxt=u; g[v].push_back(tmp); ans+=w; } dfs (x,0); printf("%lld\n",ans*2-mmax); return 0; }
原文:https://www.cnblogs.com/xidian-mao/p/9696901.html