首页 技术 正文
技术 2022年11月23日
0 收藏 423 点赞 2,161 浏览 1816 个字

链接: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);
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141632.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站