AcWing 847. 图中点的层次
原题链接
简单
距离为1的最短路,bfs是通解
import java.util.*;
public class Main {
static int n;
static int m;
static final int N = 100010;
static final int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0;
static int[] q = new int[N];
static int[] d = new int[N];
static int hh = 0;
static int tt = -1;
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
private static int bfs(int u) {
d[u] = 0;
q[++tt] = u;
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return 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++) {
d[i] = -1;
h[i] = -1;
}
while (m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
}
System.out.println(bfs(1));
}
}