$$\color{Red}{图中点的层次——详细解析——三种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

本质就是bfs，只需要记得初始化数组元素的值就可以，详细看代码

java 容器版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {
    static int N = 100010, n, m, idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] d = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static LinkedList<Integer> q = new LinkedList<Integer>();

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void bfs() {
        q.add(1);
        d[1] = 0;
        while (!q.isEmpty()) {
            int x = q.remove();
            for (int i = h[x]; i != -1; i=ne[i]) {
                int j = e[i];
                if (d[j] == 0x3f3f3f3f){
                    d[j] = d[x] + 1;
                    q.add(j);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(d, 0x3f3f3f3f);
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a, b);
        }
        bfs();
        System.out.println(d[n]);
    }
}

java 朴素代码

import java.util.*;

public class Main {
    static int N = 100010, n, m, idx = 0;
    static int e[] = new int [N];
    static int ne[] = new int [N];
    static int h[] = new int [N];
    static int d[] = new int [N];
    static int q[] = new int [N];


    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public static void bfs() {
        int hh = 0, tt = 0;
        q[0] = 1;
        d[1] = 0;

        while (hh <= tt) {
            int t = q[hh++];
            for(int i=h[t]; i!=-1; i=ne[i]) {
                int x = e[i];
                if (d[x] == -1) {
                    d[x] = d[t] + 1;
                    q[++tt] = x;
                }
            }
        }

        System.out.println(d[n]);
    }

    public static void main(String [] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0; i<N; i++) {
            h[i] = d[i] = -1;
        }
        for(int i=0; i<m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            add(a, b);
        }

        bfs();
    }
}

python3 代码

N = int(1e5 + 10)
e = [0] * N
ne = [0] * N
h = [-1] * N
d = [-1] * N
idx = 0

def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

def bfs():
    d[1] = 0
    q = [1]
    while q:
        a = q.pop(0)
        i = h[a]
        while i != -1:
            j = e[i]
            if d[j] == -1:
                d[j] = d[a] + 1
                q.append(j)
            i = ne[i]

    return d[n]

if __name__ == '__main__':
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        add(a, b)
    print(bfs())

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int e[N], ne[N], h[N], idx;
int d[N], q[N];
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}

int bfs()
{
    memset(d, -1, sizeof d);
    int hh = 0, tt = 0;
    q[0] = 1;
    d[1] = 0;
    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i!=0; i=ne[i])
        {
            int u = e[i];
            if(d[u] == -1)
            {
                d[u] = d[t] + 1;
                q[++tt] = u;
            }
        }

    }
    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    int a, b;
    while(m--)
    {
        scanf("%d%d", &a, &b);
        add(a,b);
    }
    cout << bfs();
    return 0;
}