思路

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

• 从 $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$ 号节点出发，想知道到达每个节点需要经过的最少步行次数。