思路

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

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

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

• 维护双端队列。
• 走权重为 $0$ 的边时用 push_front。
• 走权重为 $1$ 的边时用 push_back。
• 复杂度：时间 $O(n)$，空间 $O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    deque<int> dq;

    dist[1] = 0;
    dq.push_front(1);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        // 0代价传送边：u -> a[u]
        int v = a[u];
        if (dist[v] > dist[u]) {
            dist[v] = dist[u];
            dq.push_front(v);
        }

        // 1代价步行边：u -> u-1
        if (u - 1 >= 1 && dist[u - 1] > dist[u] + 1) {
            dist[u - 1] = dist[u] + 1;
            dq.push_back(u - 1);
        }

        // 1代价步行边：u -> u+1
        if (u + 1 <= n && dist[u + 1] > dist[u] + 1) {
            dist[u + 1] = dist[u] + 1;
            dq.push_back(u + 1);
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << dist[i];
    }
    cout << '\n';
    return 0;
}

Python

import sys
from collections import deque

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(next(it))

    INF = 10**9
    dist = [INF] * (n + 1)
    dq = deque()

    dist[1] = 0
    dq.appendleft(1)

    while dq:
        u = dq.popleft()

        # 0代价传送边：u -> a[u]
        v = a[u]
        if dist[v] > dist[u]:
            dist[v] = dist[u]
            dq.appendleft(v)

        # 1代价步行边：u -> u-1
        if u - 1 >= 1 and dist[u - 1] > dist[u] + 1:
            dist[u - 1] = dist[u] + 1
            dq.append(u - 1)

        # 1代价步行边：u -> u+1
        if u + 1 <= n and dist[u + 1] > dist[u] + 1:
            dist[u + 1] = dist[u] + 1
            dq.append(u + 1)

    print(' '.join(str(dist[i]) for i in range(1, n + 1)))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s == null || s.isEmpty()) return;
        int n = Integer.parseInt(s.trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(st.nextToken());

        final int INF = Integer.MAX_VALUE / 4;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        Deque<Integer> dq = new ArrayDeque<>();

        dist[1] = 0;
        dq.addFirst(1);

        while (!dq.isEmpty()) {
            int u = dq.pollFirst();

            // 0代价传送边：u -> a[u]
            int v = a[u];
            if (dist[v] > dist[u]) {
                dist[v] = dist[u];
                dq.addFirst(v);
            }

            // 1代价步行边：u -> u-1
            if (u - 1 >= 1 && dist[u - 1] > dist[u] + 1) {
                dist[u - 1] = dist[u] + 1;
                dq.addLast(u - 1);
            }

            // 1代价步行边：u -> u+1
            if (u + 1 <= n && dist[u + 1] > dist[u] + 1) {
                dist[u + 1] = dist[u] + 1;
                dq.addLast(u + 1);
            }
        }

        StringBuilder out = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.append(' ');
            out.append(dist[i]);
        }
        System.out.println(out.toString());
    }
}

题目内容

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

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

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

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

输入描述

输入两行，第一行包含一个数字 $n(1<=n<=100000)$ ，表示有 $n$ 个节点。

接下来一行 $n$ 个数字，每个数字 $a_i(1<=a_i<=n)$ ，表示 $i$ 节点的传送门可以传送到 $a_i$ 节点，注意 $a_i$ 可能等于 $i$

输出描述

输出一行包含 $n$ 个数字，第 $i$ 个数字 $ans_i$ ，表示从 $1$ 号节点到 $i$ 号节点的最少步行次数

样例1

输入

3
1 2 3

输出

0 1 2

样例2

输入

4
4 2 3 1

输出

0 1 1 0