首页 > 试题广场 >

树上最短链

[编程题]树上最短链
  • 热度指数：2414 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个地区有 个城市以及 条无向边，每条边的时间边权都是 ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。
但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

进阶：时间复杂度，空间复杂度

输入描述:
第一行一个正整数 ，含义如题面所述。
第二行  个正整数 ，代表每个城市的等级。
接下来  行每行两个正整数 ，代表一条无向边。
保证给出的图是一棵树。
 。
 。
。


输出描述:
仅一行一个整数代表答案，如果无法满足要求，输出  。
示例1

输入

3
1 2 1
1 2
2 3

输出

2
算法知识视频讲解
开通博客
头像 CUG23届硕士毕业生
发表于 2022-04-11 17:23:33
树上BFS问题 题意简述： n个城市有n-1条无向边的连通图（也是树结构），每条边的时间权值都是1； 每个城市有一个等级，求以等级相同的任意两城市作为起点和终点时，最小的时间花费。（每条边至多经过一次） 算法设计 我们可以以任意结点为起点，以其他任意结点为终点，基本上就是《任意两点间的最短路径问题》 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客937932357号
发表于 2021-08-28 13:31:03
import java.util.*;public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int n = scann 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 赫he
发表于 2023-05-14 15:23:34
#include <iostream> #include <algorithm> #include <cmath> #include <queue> #include <cstring> using namespace std; //无向边 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不想看论文
发表于 2022-03-24 23:06:05
java版——用深度优先遍历和广度优先遍历求最短路径 深度优先遍历 import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scan 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
17条回答 6444浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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