847. 图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤105
输入样例：

  1. 4 5
  2. 1 2
  3. 2 3
  4. 3 4
  5. 1 3
  6. 1 4

输出样例：

  1. 1

思路

类型：带环的权重一致的最短路问题
类似与走迷宫问题，从数组变成了图，其它基本一致。

  1. import java.util.*;
  3. public class Main {
  4.     static int n, m, idx;
  5.     static int[] h, e, ne;
  6.     static int[] dist;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt();
  11.         m = sc.nextInt();
  12.         h = new int[n + 1];
  13.         Arrays.fill(h, -1);
  14.         e = new int[m];
  15.         ne = new int[m];
  17.         dist = new int[n + 1];
  19.         while (m-- > 0) {
  20.             int a, b;
  21.             a = sc.nextInt();
  22.             b = sc.nextInt();
  24.             add(a , b);
  25.         }
  27.         bfs();
  29.         System.out.println(dist[n]);
  30.     }
  32.     static void add(int a, int b) {
  33.         e[idx] = b;
  34.         ne[idx] = h[a];
  35.         h[a] = idx++;
  36.     }
  38.     static void bfs() {
  39.         Arrays.fill(dist, -1);
  40.         dist[1] = 0;
  41.         Queue<Integer> q = new LinkedList<>();
  43.         q.offer(1);
  45.         while (!q.isEmpty()) {
  46.             int cur = q.poll();
  48.             for (int i = h[cur]; i != -1; i = ne[i]) {
  49.                 int j = e[i];
  50.                 if (dist[j] == -1) {
  51.                     dist[j] = dist[cur] + 1;
  52.                     q.offer(j);
  53.                 }
  54.             }
  55.         }
  57.     }
  58. }