import java.util.*;

public class Main{
    //使用数组模拟链表来实现宽度优先搜索
    static int N = 100010;
    static int[] h = new int[N];//存储节点
    static int[] e = new int[N];//存储值
    static int[] ne = new int[N];//存储该节点下一个值
    static int[] d = new int[N];//存储距离
    static int n;
    static int idx;
    static Queue<Integer> q = new LinkedList();//存储该几点可以向下遍历的值

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
          n = sc.nextInt();
        int m = sc.nextInt();
         Arrays.fill(h,0,n+ 1,-1);
         Arrays.fill(d,-1);

        while(m-- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a,b);
        }

        System.out.print(bfs(1));
    }
    static void add(int a,int b){//头插法插入值
        e[idx] = b;ne[idx] = h[a];h[a] = idx++;
    }
    static int bfs(int u){
        //初始化
        q.offer(u);
        d[1] = 0;
        while(!q.isEmpty()){
           int t = q.poll();
    //遍历是为了查看该节点可以向下的值或节点
           for(int i = h[t];i != -1;i = ne[i]){
              int j = e[i];
               if(d[j] == -1){//距离为-1说明还没被遍历过
                   d[j] = d[t] + 1;//距离加一
                   q.offer(j);//存储该几点可以向下遍历的值
               }
           }
        }
        return d[n];
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla