这道题是一道经典的状态压缩二进制枚举 图论最短路的问题。 核心解题思路1. 状态压缩二进制枚举题目中分部的数量 n 最大为 10这是一个非常小的数据规模。我们可以用一个 n 位的二进制数掩码 mask来表示所有分部的开闭状态。1 表示该分部保持开启0 表示关闭。我们只需要遍历 0 到 2^n - 1 的所有状态即可。2. 多源最短路Floyd 算法对于每一种分部开启的状态我们需要判断“剩余开启的分部之间两两的最远距离是否不超过 maxDistance”。这就转化为了一个求多源最短路径的问题。由于 n 很小直接使用代码简单且能求出任意两点最短路的 Floyd 算法是最合适的。3. 具体步骤* 预处理所有道路的邻接矩阵注意两个分部之间可能有多条道路要保留最短的那条。* 遍历所有 2^n 种开闭状态。* 针对当前状态复制一份邻接矩阵只保留开启分部之间的道路。* 运行 Floyd 算法计算当前开启分部之间的最短距离。* 检查所有开启分部两两之间的距离如果都小于等于 maxDistance则该方案可行结果加一。️ Java 代码实现class Solution {public int numberOfSets(int n, int maxDistance, int[][] roads) {// 1. 初始化邻接矩阵填充一个极大值final int INF 1_000_000;int[][] graph new int[n][n];for (int i 0; i n; i) {java.util.Arrays.fill(graph[i], INF);graph[i][i] 0; // 自己到自己的距离为0}// 2. 填充道路距离注意处理重边保留最短的一条for (int[] road : roads) {int u road[0], v road[1], w road[2];graph[u][v] Math.min(graph[u][v], w);graph[v][u] Math.min(graph[v][u], w);}int res 0;// 3. 二进制枚举所有分部的开闭状态 (0 到 2^n - 1)for (int mask 0; mask (1 n); mask) {// 复制当前图的邻接矩阵用于当前状态的Floyd计算int[][] dist new int[n][n];for (int i 0; i n; i) {System.arraycopy(graph[i], 0, dist[i], 0, n);}// 4. 针对当前mask只保留开启分部bit为1之间的直接道路// 关闭的分部相当于从图中移除与之相连的道路不可通行for (int i 0; i n; i) {for (int j 0; j n; j) {// 如果i或j任意一个分部在当前状态是关闭的则它们之间的直接道路不可用if (((mask i) 1) 0 || ((mask j) 1) 0) {dist[i][j] INF;}}}// 记得把自己到自己的距离设回0for (int i 0; i n; i) {if (((mask i) 1) 1) {dist[i][i] 0;}}// 5. 运行 Floyd 算法计算当前开启分部之间的最短路径for (int k 0; k n; k) {// 只有当中间点k是开启状态时才能作为中转站if (((mask k) 1) 1) {for (int i 0; i n; i) {if (((mask i) 1) 1) {for (int j 0; j n; j) {if (((mask j) 1) 1) {dist[i][j] Math.min(dist[i][j], dist[i][k] dist[k][j]);}}}}}}// 6. 检查当前方案是否可行所有开启分部两两之间的距离不超过 maxDistanceboolean isValid true;for (int i 0; i n; i) {if (((mask i) 1) 1) {for (int j i 1; j n; j) {if (((mask j) 1) 1 dist[i][j] maxDistance) {isValid false;break;}}}if (!isValid) break;}if (isValid) {res;}}return res;}} 复杂度分析* 时间复杂度O(2^n × n³)。我们需要枚举 2^n 种状态每种状态下运行一次 Floyd 算法其时间复杂度为 O(n³)。因为 n 10计算量大约在 1024 * 1000 ≈ 10⁶ 级别完全可以在规定时间内通过。* 空间复杂度O(n²)。主要消耗在于存储图的邻接矩阵和每次计算最短路的距离矩阵。