星际旅行——Dijkstral_堆优化

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // 用于读取输入
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); // 用于输出结果

    public static void main(String[] args) throws IOException {
        String[] s = in.readLine().split("\\s"); // 读取一行数据，包含星球数量、连接数和查询次数
        int n = Integer.parseInt(s[0]); // 星球数量
        int m = Integer.parseInt(s[1]); // 连接数
        int q = Integer.parseInt(s[2]); // 查询次数

        // 优先队列用于Dijkstra算法，存储星球及到达该星球的最短距离
        PriorityQueue<long[]> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1[1], o2[1]));

        // 数组列表数组，用于存储星球之间的连接关系和距离
        List<int[]>[] list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) list[i] = new ArrayList<>();

        // 二维数组，存储星球之间的距离，初始值设为Long.MAX_VALUE
        long[][] map = new long[n + 1][n + 1];
        for (long[] v : map) Arrays.fill(v, Long.MAX_VALUE);

        // 读取连接关系，将连接关系存储在list数组中
        int a, b;
        for (int i = 0; i < m; i++) {
            s = in.readLine().split("\\s");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            list[a].add(new int[]{b, 1});
            list[b].add(new int[]{a, 1});//！！！注意是双向连接！！！
        }

        // 使用Dijkstra算法计算每个星球到其他星球的最短距离，并存储在map数组中
        for (int i = 1; i <= n; i++) {
            map[i][i] = 0L;
            pq.add(new long[]{i, 0L});
            while (!pq.isEmpty()) {
                long[] v = pq.poll();
                for (int[] x : list[(int) v[0]]) {
                    if (v[1] + x[1] < map[i][x[0]]) {
                        map[i][x[0]] = v[1] + x[1];
                        pq.add(new long[]{x[0], map[i][x[0]]});
                    }
                }
            }
        }

        // 统计查询结果
        long sum = 0L;
        for (int k = 0; k < q; k++) {
            s = in.readLine().split("\\s");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            for (int i = 1; i <= n; i++) {
                if (map[a][i] <= b) sum++;
            }
        }

        // 计算平均可到达星球数量，并输出结果
        out.printf("%.2f", 1.0 * sum / q);
        out.flush();
    }
}