19726 星际旅行

⭐️难度：困难
🌟考点：Dijkstra、省赛、最短路问题、期望、2024
📖

📚

import java.util.*;public class Main {static int N = 1005;static ArrayList<Integer>[] g = new ArrayList[N]; // 无向图，存Integer,有向图存数组static boolean[] vis = new boolean[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int Q = sc.nextInt();// 无向图for (int i = 0; i < m; i++) {int a = sc.nextInt();int b = sc.nextInt();addEdge(a,b);addEdge(b,a);//无向图，加两次边}int ans = 0;for (int i = 0; i < Q; i++) {int x = sc.nextInt();int y = sc.nextInt();ans += solve(x,y);}System.out.printf("%.2f",(double)ans / Q);// 将 ans 转换为 double 类型进行除法运算}static void addEdge(int u,int v){if(g[u] == null) g[u] = new ArrayList<>();g[u].add(v);}static int solve(int x,int y){Queue<int[]> q = new LinkedList<>();Arrays.fill(vis,false);q.add(new int[]{x,0});vis[x] = true;int res = 1;while(!q.isEmpty()){int[] cur = q.poll();if(cur[1] >= y) continue;if(g[cur[0]] == null) continue;for(int v : g[cur[0]]){if(vis[v]) continue;vis[v] = true;res ++;q.add(new int[]{v,cur[1]+1});}}return res;}
}

🍎笔记