这道题是一道经典的状态压缩（二进制枚举）+ 图论（最短路）的问题。
💡 核心解题思路
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;
}
}
}
// 记得把自己到自己的距离设回0
for (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. 检查当前方案是否可行：所有开启分部两两之间的距离不超过 maxDistance
boolean 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²)。主要消耗在于存储图的邻接矩阵和每次计算最短路的距离矩阵。
