装修建材网站,黄浦区网站建设公司,广西电力工程建设有限公司网站,国内永久免费的crm这道题用的是bfs#xff0c;一开始用了dfs搜出了答案为4
题目
给定一个 n个点 m 条边的有向图#xff0c;图中可能存在重边和自环。
所有边的长度都是 1#xff0c;点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离#xff0c;如果从 1 号点无法走到 n 号点…这道题用的是bfs一开始用了dfs搜出了答案为4
题目
给定一个 n个点 m 条边的有向图图中可能存在重边和自环。
所有边的长度都是 1点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离如果从 1 号点无法走到 n 号点输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行每行包含两个整数 a 和 b表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数表示 1 号点到 n号点的最短距离。
数据范围
1≤n,m≤10
输入样例
4 5
1 2
2 3
3 4
1 3
1 4输出样例
1解析与代码
bfs的模版思路 使用队列保存待访问的节点。 初始化距离数组d 数组为 -1表示节点未被访问。 将起始节点放入队列并设置距离为 0。 队列非空时循环执行以下步骤 弹出队首节点。遍历该节点的相邻节点。如果相邻节点未被访问更新距离并将相邻节点入队。 返回目标节点的距离。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n, m, idx, N 100010, ans Integer.MAX_VALUE;static int[] e new int[N * 2], h new int[N * 2], ne new int[N * 2], d new int[N * 2];static boolean[] state new boolean[N];// 添加边建立邻接表public static void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx ;}public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();m in.nextInt();Arrays.fill(h, -1);// 构建图的邻接表for (int i 0; i m; i) {int a in.nextInt();int b in.nextInt();add(a, b);}System.out.println(bfs());}public static int bfs() {Arrays.fill(d, -1);QueueInteger q new LinkedList();d[1] 0;q.offer(1);while (!q.isEmpty()) {int t q.poll();// 遍历与当前节点 t 相邻的节点for (int i h[t]; i ! -1; i ne[i]) {int j e[i];if (d[j] ! -1) continue; // 如果节点已经访问过跳过d[j] d[t] 1; // 更新节点 j 的距离q.offer(j); // 将节点 j 入队}}return d[n]; // 返回目标节点 n 的距离}
}
