1 solutions
-
0
题面描述
在这道题中,我们需要帮助塔子规划从起点星球到终点星球的最短路径,给定的路径由若干通行证定义。输入包括通行证的数量和起点、终点的编号,以及每个通行证的起止星球。输出应为塔子需要经过的星球数量(不包括起点),若无法到达终点,则返回 -1。我们可以使用广度优先搜索(BFS)算法来解决此问题,通过构建星球间的图结构,逐层探索可达星球,以找到最短路径或判断不可达。
思路: bfs
朴素的bfs求最短路的题
算法步骤:
- 图的表示:使用邻接表来表示图。对于每个通行证(边),将起点和终点加入到相应的列表中。
- 初始化:创建一个数组
vis
用于标记每个星球是否被访问过,以及记录到达该星球所需的步数。 - BFS搜索:
- 初始化队列,将起点放入队列。
- 进行循环,直到队列为空。在每一层中,遍历当前层的所有星球,并对每个星球的相邻星球进行处理。
- 如果相邻星球尚未被访问,则更新其访问步数,并将其加入队列。
- 步数在每一层结束时自增,确保每次都能正确计算到达每个星球的最小步数。
- 结果输出:检查终点星球的访问步数,如果仍为 0,则表示不可达,输出 -1;否则输出访问步数。
代码
C++
Python
Java
- 1
Information
- ID
- 41
- Time
- 2000ms
- Memory
- 512MiB
- Difficulty
- 6
- Tags
- # Submissions
- 414
- Accepted
- 109
- Uploaded By