题目链接蓝桥云课星际旅行洛谷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] 14. 动态规划更新最短路径枚举中间节点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统计满足条件的节点总数 ret6. 计算并输出期望将所有查询的可达节点数累加得到总和 cnt计算平均值期望cnt / q其中 q 是查询总次数最后按照题目要求保留两位小数输出Java代码import java.util.*; public class Main{ public static void main(String[] args){ Scanner scnew Scanner(System.in); int nsc.nextInt();//图的总节点数 int msc.nextInt();//图的总边数 int qsc.nextInt();//查询的总次数 //distance[i][j]:i节点到j节点的最短路径长度 int[][] distancenew int[n1][n1]; //初始化为无穷大表示未连通 for(int i0;in;i){ Arrays.fill(distance[i],0x3f3f3f3f); //自己到自己距离为0 distance[i][i]0; } //处理m条边给无向图的边赋权值 for(int i0;im;i){ int asc.nextInt(); int bsc.nextInt(); distance[a][b]1; distance[b][a]1; } //动态规划枚举中间节点k更新i→k→j是否比i→j更短 for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) distance[i][j]Math.min(distance[i][k]distance[k][j],distance[i][j]); //处理所有查询统计总可达节点数计算期望 double cnt0; //循环处理q个查询 for(int i0;iq;i){ int startsc.nextInt(); int usecntsc.nextInt();//可用传送门次数 int ret0; for(int j1;jn;j) if(distance[start][j]usecnt) ret; cntret; } //计算并输出期望 System.out.println(String.format(%.2f,cnt/q)); sc.close(); } }