题目描述

明明暑假来济南旅游旅游，他打算游玩N个旅游景点，N-1条双向连接的道路将它们联通起来，每一条道路有固定长度。一开始明明位于1号景点。

现在希望你能够求出旅行长度最小的方案，使得每个景点至少被访问到一次。

 

 

输入

第一行两个整数N，代表景点数目。

接下来N-1行，每行三个整数s, t, w，表示有一条从s到t的双向道路，长度为w。s和t的编号从1开始。

 

输出

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

 

#include
      
       #define ll long longusing namespace std;const int INF=0x3f3f3f3f;const int maxn=50005;struct Edge{    int v;    int cost;    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}};vector
       
         E[maxn];void addedge(int u,int v,int w){    E[u].push_back(Edge(v,w));}bool vis[maxn];int cnt[maxn];int dist[maxn];bool spfa(int st,int n){    memset(vis,false,sizeof vis);    for(int i=1;i<=n;i++)        dist[i]=INF;    vis[st]=true;    dist[st]=0;    queue
        
         qu;    while(!qu.empty())    {        qu.pop();    }    qu.push(st);    memset(cnt,0,sizeof cnt);    cnt[st]=1;    while(!qu.empty())    {        int u=qu.front();        qu.pop();        vis[u]=false;        for(int i=0;i
         
          dist[u]+E[u][i].cost)            {                dist[v]=dist[u]+E[u][i].cost;                if(!vis[v])                {                    vis[v]=true;                    qu.push(v);                    if(++cnt[v]>n)                        return false;                }            }        }    }    return true;}int vis0[50005];int main(){    int n;    scanf("%d",&n);    int u, v, w;    int ant=0,mx=0;    for (int i = 1; i <= n-1; i++)    {        scanf("%d %d %d",&u,&v,&w);        ant+=w;        addedge(u,v,w);        addedge(v,u,w);        vis0[u]=0;        vis0[v]=1;    }    ant*=2;    spfa(1,n);    for(int i=1;i<=n;i++)    {        mx=max(mx,dist[i]);    }    printf("%d\n",ant-mx);    return 0;}