华为机考-树上逃离

简介: 华为机考-树上逃离

题目


给定一棵树,这个树有n个节点,节点编号从0开始依次递增,0固定为根节点。在这棵树上有一个小猴子,初始时该猴子位于根节点(0号) 上,小猴子一次可以沿着树上的边从一个节点挪到另一个节点,但这棵树上有一些节点设置有障碍物,如果某个节点上设置了障碍物,小猴子就不能通过连接该节点的边挪动到该节点上。问小猴子是否能跑到树的叶子节点(叶子节点定义为只有一条边连接的节点),如果可以,请输出小猴子跑到叶子节点的最短路径(通过的边最少),否则输出字符串NULL。


输入


第一行给出数字n,表示这个树有n个节点,节点编号从0开始依次递增,0固定为根节点,1<=n<10000

第二行给出数字edge,表示接下来有edge行,每行是一条边

接下来的edge行是边: x y,表示x和y节点有一条边连接

边信息结束后接下来的一行给出数字block,表示接下来有block行,每行是个障碍物

接下来的block行是障碍物: X,表示节点x上存在障碍物

输出

如果小猴子能跑到树的叶子节点,请输出小猴子跑到叶子节点的最短路径(通过的边最少),比如小猴子从0经过1到达2 (叶子节点) ,那么输出“0->1->2”,否则输出“NULL”。注意如果存在多条最短路径,请按照节点序号排序输出,比如0->1和0->3两条路径,第一个节点0一样,则比较第二个节点1和3,1比3小,因此输出0->1这条路径。


样例


1. 2
2. 1
3. 0 1
4. 1
5. 1
6. 
7. 4
8. 3
9. 0 1
10. 0 2
11. 0 3
12. 1
13. 2
14. 
15. 7
16. 6
17. 0 1
18. 0 3
19. 1 2
20. 3 4
21. 1 5
22. 5 6
23. 1
24. 5
25. 
26. 4
27. 3
28. 0 1
29. 0 2
30. 0 3
31. 2
32. 2
33. 3

思路


使用广度优先搜索寻找最短路径

1. from collections import deque
2. 
3. n=int(input())
4. map = {}
5. edge = int(input())
6. for _ in range(edge):
7.     l, r = input().split(' ')
8.     l,r = int(l),int(r)
9. if l not in map: map[l]=[]
10. if r not in map: map[r]=[]
11. map[l].append(r)
12. map[r].append(l)
13. 
14. block = int(input())
15. blocks = set()
16. for i in range(block):
17.     blocks.add(int(input()))
18. 
19. def solve():
20.     queue=deque()
21.     queue.append([0,[0]])
22.     vis = set()
23.     vis.add(0)
24. while len(queue):
25.         node,path = queue.popleft()
26. if node!=0 and len(map[node])==1:
27. print(str(path)[1:-1].replace(",","->").replace(" ",""))
28. return
29. for item in map[node]:
30. if item not in blocks and item not in vis:
31.                 queue.append([item,path+[item]])
32.                 vis.add(item)
33. print("NULL")
34. 
35. solve()
目录
打赏
0
0
0
0
8
分享
相关文章
最全解决docker配置kibana报错 Kibana server is not ready yet
最全解决docker配置kibana报错 Kibana server is not ready yet
1528 0
K8s集群实战:使用kubeadm和kuboard部署Kubernetes集群
总之,使用kubeadm和kuboard部署K8s集群就像回归童年一样,简单又有趣。不要忘记,技术是为人服务的,用K8s集群操控云端资源,我们不过是想在复杂的世界找寻简单。尽管部署过程可能遇到困难,但朝着简化复杂的目标,我们就能找到意义和乐趣。希望你也能利用这些工具,找到你的乐趣,满足你的需求。
391 33
电商API:销量监控与竞品分析利器
电商数据接口API在现代电商运营中至关重要,可实现品牌价格、销量、评论等数据监控,优化销售策略。接入主流平台如淘宝、天猫、京东等API,或使用RPA技术取数,保障数据安全与效率。通过数据库连接、ERP直连等方式整合分析数据,监控竞品与价格,掌握市场动态。同时,注重数据安全性、技术支持及成本效益,助力企业在竞争中脱颖而出,提升业务效率与竞争力。
81 0
HelloMeme:开源的面部表情与姿态迁移框架,将视频中的人物表情迁移到静态图像中生成动态视频
HelloMeme 是一个基于 Stable Diffusion 1.5 模型的面部表情与姿态迁移框架,通过集成空间编织注意力机制,实现了自然且物理合理的表情包视频生成。该框架具有强大的泛化能力和扩展性,适用于多种应用场景。
241 77
HelloMeme:开源的面部表情与姿态迁移框架,将视频中的人物表情迁移到静态图像中生成动态视频
数据库数据恢复—Mysql数据库表记录丢失的数据恢复方案
Mysql数据库故障: Mysql数据库表记录丢失。 Mysql数据库故障表现: 1、Mysql数据库表中无任何数据或只有部分数据。 2、客户端无法查询到完整的信息。
支付宝 网站支付Demo 案例【沙箱环境】IDEA如何配置启动Eclipse项目
该博客文章讲述了如何在IntelliJ IDEA中配置和启动一个使用Eclipse开发的支付宝网站支付Demo案例。文章详细记录了从导入项目到配置Tomcat,再到解决启动过程中遇到的问题的步骤。作者还分享了在IDEA中遇到的一些常见问题,如项目配置、依赖库添加、编码问题等,并提供了相应的解决方案。此外,文章还提供了支付效果的展示以及一些支付宝案例文档中需要修改的参数信息。
支付宝 网站支付Demo 案例【沙箱环境】IDEA如何配置启动Eclipse项目
Kubernetes(K8S) kubesphere 安装
Kubernetes(K8S) kubesphere 安装
257 4
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
4689 1
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问