旅行商问题【山财新生赛E】-白红宇

旅行商问题【山财新生赛E】

阅读量：6960 次

发布时间：2019-06-27

本文共 1989 字，大约阅读时间需要 6 分钟。

链接：

来源：牛客网

题目描述

旅行商来到了一个新的国家，这个国家有N个城市，他们直接由N-1条道路相连接，每条道路的长度不尽相同

旅行商现在在1号城市，若他要每一个城市都游览一遍，他需要行走的最短路程是多少？

输入描述:

第一行一个数N （50000>N>1）代表城市个数之后N-1行每行三个数x y z代表从x到y的距离为z

输出描述:

输出最小距离

示例1

输入

31 2 11 3 1

输出

思路： N个城市，N-1条道路，如果要走遍所有的城市，只要有一个城市与>1个城市有路，那么就一定会有走回头路。

呢么要求权值最小的最短路程，就是让尽量回头路那段路程小。

假设把所有的道路都来回走一遍，找一次性能走的最长的一条路，那么剩下没走的就是最短的回头路了

用dfs找那条权值最大的那条路因为要求这条路是不走回头路的，所以记录走到的点的父节点，不往父节点走

最后最短路程为 sum * 2 - imax;

#include
     
      #include
      
            //EOF,NULL#include
       
            //memset#include
        
             //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc#include
         
                     //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))#include
          
            //fill,reverse,next_permutation,__gcd,#include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                   //setw(set_min_width),setfill(char),setprecision(n),fixed,#include
                  
                   #include
                   #include
                    
                     #include
                     
                       //INT_MAX#include
                      
                        // bitset
                        nusing namespace std;typedef long long LL;typedef long long ll;typedef pair
                       
                         P;#define all(x) x.begin(),x.end()#define readc(x) scanf("%c",&x)#define read(x) scanf("%d",&x)#define read2(x,y) scanf("%d%d",&x,&y)#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define print(x) printf("%d\n",x)#define mst(a,b) memset(a,b,sizeof(a))#define lowbit(x) x&-x#define lson(x) x<<1#define rson(x) x<<1|1#define pb push_back#define mp make_pairconst int INF =0x3f3f3f3f;const int mod = 1e9+7;const int MAXN = 1000000+5;LL ans = 0;LL dis[MAXN];ll imax = 0;vector
                        
                         
                           > V[MAXN];void dfs(int pre,int fa){ for(int i = 0 ; i < V[pre].size(); i++){ LL v = V[pre][i].first ; LL d = V[pre][i].second; if(v != fa){ dis[v] = dis[pre] + d; dfs(v,pre); } } imax = max(imax,dis[pre]);}int main(){ int n ; read(n); LL x,y,z; LL sum = 0; for(int i = 1 ; i< n; i++){ scanf("%lld%lld%lld",&x,&y,&z); V[x].pb(mp(y,z)); V[y].pb(mp(x,z)); sum += z; } dis[1] = 0; dfs(1,0); print(sum * 2 -imax);}