曦皓的旅游

【题目描述】

曦皓要去一个国家旅游。

这个国家有N个旅游景点，N-1条双向连接的道路将它们连通起来，每一条道路都有一个固定长度，一开始曦皓位于1号景点。

现需要求出旅行长度最小的方案，使得每个景点至少被访问到一次。

【输入描述】

第一行输入一个整数N，表示景点数目；

接下来N-1行，每行输入三个整数s、t、w，表示存在一条从s到t的双向道路，长度为w。

【输出描述】

输出一个整数，表示能够访问每个景点至少一次的方案的最小旅行长度。

【样例输入】

样例1：

3

1 2 3

2 3 3

 

样例2：

3

1 2 3

1 3 3

【样例输出】

样例1：

6

 

样例2：

9

【数据范围及提示】

对于30%的数据，1 ≤ N ≤ 10；

对于70%的数据，1 ≤ N ≤ 1000；

对于100%的数据，1 ≤ N ≤ 50000，1 ≤ w ≤ 1000。

源代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,Num(0),Head[50001],f[50001],Sum[50001];
struct Node
{
    int S,To,Next;
}Edge[100001];
void Add(int t1,int t2,int t) //边表。
{
    Edge[++Num].S=t;
    Edge[Num].To=t2;
    Edge[Num].Next=Head[t1];
    Head[t1]=Num;
}
void DFS(int t,int Father) //通用树上DFS。
{
    for (int a=Head[t];a;a=Edge[a].Next)
      if (Edge[a].To!=Father)
      {
        int T=Edge[a].To;
        Sum[T]=Edge[a].S<<1; //因为要来回嘛。
        DFS(T,t);
        Sum[t]+=Sum[T]; //总路程。
        f[t]=max(f[T]+Edge[a].S,f[t]); //找出最长链。
      }
}
int main() //竟然没看见它是一棵树。
{
    scanf("%d",&n);
    for (int a=1;a<n;a++)
    {
        int t,t1,t2;
        scanf("%d%d%d",&t1,&t2,&t);
        Add(t1,t2,t);
        Add(t2,t1,t);
    }
    DFS(1,0);
    printf("%d",Sum[1]-f[1]); //不走最长链就可以了，其实是个贪心。
    return 0;
}