首页 > 试题广场 >

反复横跳

[编程题]反复横跳
  • 热度指数：97 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给出一张带权无向图，图中任意两点间有且仅有一条路径。计算从任意点出发并访问完所有节点经过边的权值之和的最小值。

输入

第一个参数为 ，

第二个参数为大小为 的点对 的集合 ，其中 表示结点 与结点 之间有一条边，

第三个参数为大小为 的整数集合 ，其中 表示第 条边的长度，

输出

权值之和的最小值

示例1

输入

5,[(1,2),(2,3),(3,4),(2,5)],[39,48,54,100]

输出

280

说明

从 4 号点出发，路径为 4 - 3 - 2 - 1 - 2 - 5。
算法知识视频讲解
开通博客
头像 摸鱼学大师
发表于 2021-09-14 20:35:17
题目的主要信息： 一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树 计算从任意点出发并访问完所有节点经过边的权值之和的最小值 分析： 首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-10-22 17:22:05
题目的主要信息： 已知带权无向图，每个节点之间仅有一条路径 求经过所有节点最小权重之和 方法一：DFS 如果不考虑路径长度，那么把所有路径走一遍必定可以经过所有节点。 要经过每一个节点，且每个节点之间只有一条路径，那么至少需要把所有的路径走一遍，假设权重之和为weight。在最坏的情况，每条路 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Bug-Maker
发表于 2021-07-13 00:29:03
所有边的两倍减去无重复最长路径就是答案。因为题目说了任意两点之间只有一条路径，所以在我们沿着最长边走的时候，所有的分支都需要走两遍，而最长路径只需要走一遍。 class Solution {public: /** * 最短距离 * @param n int整型 * @p 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 George_Plover
发表于 2021-09-13 11:28:39
题意整理： 基本题意 ​ 给出一棵具有 个结点的无根树，给出每条边的边权 ，表示两个结点之间的距离。 ​ 可以任意选择一个结点作为起点，按照一定的顺序访问每个结点至少一次，问经过的路径的总长度最少是多少。输出这个答案。 数据范围与性质 ​ 。 ​ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-09-08 17:04:38
题意整理 给定一张带权无向图，图中任意两点间有且仅有一条路径。 求从任意点出发，访问完所有节点后，所经过边的权值和的最小值。 方法一（dfs） 1.解题思路 要想边权值最小，所走的路径中必定包含了最长（边权值最大）无重复节点的路径，只要求出这个路径权值和，用所有路径权值和的两倍减去最大路径权值和 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 搜索 图
难度：
0条回答 1458浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号