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

冷不防 2022-01-06 07:27 165阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/547/E][https_ac.nowcoder.com_acm_contest_547_E]  
来源：牛客网

## 题目描述 ##

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

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

## 输入描述: ##

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

## 输出描述: ##

输出最小距离

示例1

## 输入 ##

3
    1 2 1
    1 3 1

## 输出 ##

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

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

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

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

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

#include<iostream>
    #include<cstdio>     //EOF,NULL
    #include<cstring>    //memset
    #include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
    #include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
    #include<algorithm>  //fill,reverse,next_permutation,__gcd,
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<utility>
    #include<iterator>
    #include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
    #include<functional>
    #include<map>
    #include<set>
    #include<limits.h>     //INT_MAX
    #include<bitset> // bitset<?> n
    using namespace std;
    
    typedef long long LL;
    typedef long long ll;
    typedef pair<int,int> 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_pair
    const int INF =0x3f3f3f3f;
    const int mod = 1e9+7;
    
    const int MAXN = 1000000+5;
    LL ans = 0;
    LL dis[MAXN];
    ll imax = 0;
    vector<pair<LL, LL> > 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);
    }

转载于:https://www.cnblogs.com/llke/p/10780132.html

[https_ac.nowcoder.com_acm_contest_547_E]: https://ac.nowcoder.com/acm/contest/547/E