首页 > 其他 > 详细

树的遍历 (走完树上所有点所需最小路程)

时间:2018-09-24 22:57:51      阅读:348      评论:0      收藏:0      [点我收藏+]

链接:https://www.nowcoder.com/acm/contest/188/C
来源:牛客网

小w不会离散数学,所以她van的图论游戏是送分的
小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次,最少需要走多少路

输入描述:

第一行两个整数 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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!