题目
给定一棵树，这个树有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()
