题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。
所有边的长度都是 1,点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。
算法
思路:求某点到某点的最短路径,bfs即可
具体代码
import java.util.*;
import java.io.*;
public class Main {
private static int N = 2 * 100010;
private static int idx = 0;
private static int[] e = new int[N];
private static int[] ne = new int[N];
private static int[] h = new int[N];
private static boolean[] st = new boolean[N];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
Arrays.fill(h, -1);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int n1 = Integer.parseInt(line[0]);
int n2 = Integer.parseInt(line[1]);
add(n1, n2);
}
int res = bfs(n, 1);
System.out.println(res);
}
private static int bfs(int n, int s) {
Queue<int[]> q = new LinkedList<>();
st[s] = true;
q.offer(new int[]{s, 0});
while (!q.isEmpty()) {
int[] info = q.poll();
int x = info[0];
int step = info[1];
if (x == n) return step;
for (int i=h[x]; i!=-1; i=ne[i]) {
int j = e[i];
if (st[j]) continue;
q.offer(new int[]{j, step+1});
st[j] = true;
}
}
return -1;
}
// 在a中插入b,使用头插法
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}