Problem: 扫雪系列I

Time Limit: 1 Sec Memory Limit: 128 MB

Description

大雪履盖了整个城市，市政府要求冬季服务部门尽快将一些街道（列在一份清单中）的积雪清除掉以恢复交通，整个城市由许多交叉路口和街道构成，当然任意两个交叉路口都是直接或间接连通的，清单给出了最少的街道，使得这些街道的积雪清除后任意两个交叉路口之间有且仅有一条通路，冬季服务部门只有一辆铲雪车及一名司机，这辆铲雪车的出发点位于某个交叉路口。无论街道上有没有积雪，铲雪车每前进一米都要消耗一升燃料，冬季服务部门要求司机在铲除清单上的所有街道的积雪的前提下，要求消耗燃料最少，积雪铲完后车可以停在任意的交叉路口。

Input

输入文件的第一行包含两个整数N和S，1≤N≤100000，1≤S≤N。N为交叉路口的总数；S为铲雪车出发的路口序号。路口的标号为1••N。
接下来的N-1行为清单上的街道，每一行包含三个用空格隔开的整数A、B、C，表示一条从交叉路口A到交叉路口B的街道，C为该街道的长度，单位为米，1≤C≤1000。

Output

输出文件仅一行包含一个整数表示清除所有积雪所需的最少的燃料数量。

Sample Input

5 1
1 2 1
2 3 1
3 5 1
3 4 1

Sample Output

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,s,sum,tot,val=-1,now[200001],son[200001],pre[200001],dist[100001],V[200001];
bool flag[100001];
void put(int  x,int y,int z)
{
    pre[++tot]=now[x];
    now[x]=tot;
    son[tot]=y;
    V[tot]=z;
}
void dfs(int u)
{
    flag[u]=1;
    for(int i=now[u];i;i=pre[i])
    {
        int v=son[i];
        if(!flag[v])
        {
            dist[v]=dist[u]+V[i];
            dfs(v);
        }
    }
}
int main()
{
    int a,b,c;
    cin>>n>>s;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        put(a,b,c);
        put(b,a,c);sum+=c;
    }
    dfs(s);
    for(int i=1;i<=n;i++)
    {
        val=max(val,dist[i]);
    }
    cout<<2*sum-val;
    return 0;
}