题目链接：

蓝桥云课：星际旅行

洛谷：P11046 [蓝桥杯 2024 省 Java B] 星际旅行

算法原理：

解法：最短路问题

时间复杂度O(n³)

1.问题建模：转化为图论最短路问题
将每个 “节点” 视为图中的顶点
将 “可直达的两个节点” 视为无向边，边权固定为 1（因为使用 1 次传送门）
问题转化为：给定起点 start，求图中与 start 的最短路径长度 ≤ 可用传送门次数的节点总数
2. 初始化：
distance[i][j] ：节点 i 到节点 j 的最短路径长度
distance[i][i] = 0：自己到自己不需要传送门
其余 distance[i][j] = 0x3f3f3f3f：用一个 “足够大的数” 表示初始时两点不连通
3. 建图
对于每条给定的边 (a, b)：
因为是无向图，所以同时设置 distance[a][b] = 1 和 distance[b][a] = 1
4. 动态规划更新最短路径

枚举中间节点k，若"i→k→j"是否比"i→j"更短就更新
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
5. 处理查询：统计可达节点数
对于每个查询 (start, usecnt)：
遍历图中所有节点 j（从 1 到 n）
如果 distance[start][j] <= usecnt，说明从 start 出发，使用不超过 usecnt 次传送门可以到达 j
统计满足条件的节点总数 ret
6. 计算并输出期望
将所有查询的可达节点数累加，得到总和 cnt
计算平均值（期望）：cnt / q，其中 q 是查询总次数

最后按照题目要求保留两位小数输出

Java代码：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//图的总节点数
        int m=sc.nextInt();//图的总边数
        int q=sc.nextInt();//查询的总次数
        //distance[i][j]:i节点到j节点的最短路径长度
        int[][] distance=new int[n+1][n+1];
        //初始化为无穷大，表示未连通
        for(int i=0;i<=n;i++){
            Arrays.fill(distance[i],0x3f3f3f3f);
            //自己到自己距离为0
            distance[i][i]=0;
        }
        //处理m条边，给无向图的边赋权值
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            distance[a][b]=1;
            distance[b][a]=1;
        }
        //动态规划：枚举中间节点k，更新"i→k→j"是否比"i→j"更短
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    distance[i][j]=Math.min(distance[i][k]+distance[k][j],distance[i][j]);
        //处理所有查询，统计总可达节点数，计算期望
        double cnt=0;
        //循环处理q个查询
        for(int i=0;i<q;i++){
            int start=sc.nextInt();
            int usecnt=sc.nextInt();//可用传送门次数
            int ret=0;
            for(int j=1;j<=n;j++)
                if(distance[start][j]<=usecnt)
                    ret++;
            cnt+=ret;
        }
        //计算并输出期望
        System.out.println(String.format("%.2f",cnt/q));
        sc.close();
    }
}