类似最小生成树

题目

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述 
小w不会离散数学，所以她van的图论游戏是送分的
小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路
输入描述:
第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路
输出描述:
一个数表示答案
示例1
输入
复制
3 1
1 2 1
2 3 1
输出
复制
2
备注:
1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647


/*
每条路最多走俩次便可访问全部节点，然后减去由起点可一次dfs最大的路径长度。即为答案，应为这次dfs是可以不用走双的。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50000 + 10;
int n,x;
struct node
{
    int t,w;
    node(){}
    node(int t,int w):t(t),w(w){}
};
vector<node> g[maxn];
int vis[maxn];
int maxx = INT_MIN;


void dfs(int v, int val)
{
    maxx=max(maxx,val);
    for(int i=0; i<g[v].size(); i++){
        node u = g[v][i];
        if(!vis[u.t]){
            vis[u.t] = 1;
            dfs(u.t, val+u.w);
            vis[u.t] = 0;
        }
    }

}
int main()
{
    cin >> n >>x;
    int f,t,w;
    int ans=0;
    for(int i=0; i<n-1; i++)
    {
        cin >>f>>t>>w;
        g[f].push_back(node(t,w));
        g[t].push_back(node(f,w));
        ans += w;
    }
    vis[x] = 1;
    dfs(x, 0);
    cout << ans*2 - maxx <<endl;
    return 0;
}