首页 > 试题广场 >

水图

[编程题]水图

小w不会离散数学，所以她van的图论游戏是送分的

小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路

第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路

一个数表示答案

示例1

输入

3 1
1 2 1
2 3 1

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

算法知识视频讲解

PARKSI

发表于 2025-01-27 18:20:13

推荐使用本链接访问，以获得更好的排版题目小w不会离散数学，所以她van的图论游戏是送分的小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度小w现在在点x上她想知道从点x出发经过每个点至少一次，最少需要走多少路输入&输出第一行两个整数 n,x,代表点展开全文

耕云种月

发表于 2022-01-30 16:54:08

原题解链接：https://ac.nowcoder.com/discuss/149984 本场饲喂量小的题目发现从xxx出发,只有一条路径可以只经过一次，其他的都会经过两次找出这条最长的路径,用所有路径权值之和*2，减去这条路径的就好了 #include<bits/stdc++.h> 展开全文

深度优先搜索(DFS)

难度：

0条回答 0收藏 47浏览

水图

扫一扫，把题目装进口袋