题目描述
blablabla
样例
import java.util.*;
class Main{
static int idx;
static int[] h, ne, e;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
init(n, m);
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt();
add(a, b);
}
System.out.println(bfs(n));
}
public static int bfs(int n) {
Queue<Integer> queue = new LinkedList<>();
int step = 0;
boolean[] visited = new boolean[n + 1];
visited[1] = true;
queue.offer(1);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int curNode = queue.poll();
if (curNode == n) return step;
for (int nextIndex = h[curNode]; nextIndex != -1; nextIndex = ne[nextIndex]) {
int nextNode = e[nextIndex];
if (visited[nextNode]) continue; // 重边 或者自环
// 如果是记录记录距离的话 int[] dis = new int[n + 1] then init with Integer.MAX
// dis[nextNode] > dis[curNode] + 1
visited[nextNode] = true;
queue.offer(nextNode);
}
}
step++;
}
return -1;
}
public static void init(int n, int m) {
idx = 0;
h = new int[n + 1];
Arrays.fill(h, -1);
ne = new int[m];
e = new int[m];
}
public static void add(int a, int b) {
ne[idx] = h[a];
h[a] = idx;
e[idx] = b;
idx++;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla