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

时间：2022-11-13 15:59:14

链接：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

输出

3

思路 ： 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+;

const int MAXN = +;

LL ans = ;

LL dis[MAXN];

ll imax = ;

vector<pair<LL, LL> > V[MAXN];

void dfs(int pre,int fa){

    for(int i =  ; 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 = ;

    for(int i =  ; 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[] = ;

    dfs(,);

    print(sum *  -imax);

}

相关文章