1000ms

Difficulty: 4

所属公司 : 拼多多

时间 :2025年8月31日

算法与标签>BFS

会员或题库专享

请先，开通会员或购买题库拼多多机考题库，可解锁完整内容。

购买拼多多机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

思路

将问题建模为带权图最短路：

从 $i$ 到 $a_i$ 的有向边，权重为 $0$ 。
从 $i$ 到 $i-1$ 、 $i+1$ 的边（若存在），权重为 $1$ 。要求从 $1$ 到所有点的最短路，权值和等于步行次数。

由于边权只为 $0$ 或 $1$ ，使用 $0$ - $1$ BFS：

题目内容

在一片神奇的魔法森林中，有 $n$ 个魔法节点，每个节点都有一个传送门。第 $i$ 个节点的传送门会把你传送到 $a_i$ 号节点。

多多每次可以选择坐传送门从 $i$ 节点传送到 $a_i$ 节点，或者选择步行到相邻的节点 $i-1$ 或 $i+1$ 节点。

当然多多是个喜欢偷懒的人，所以它能坐传送门就尽量不步行。

现在多多从 $1$ 号节点出发，想知道到达每个节点需要经过的最少步行次数。