func numberOfSets(n, maxDistance int, roads [][]int) int {
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = math.MaxInt / 2 // 防止加法溢出
}
}
for _, e := range roads {
x, y, wt := e[0], e[1], e[2]
g[x][y] = min(g[x][y], wt)
g[y][x] = min(g[y][x], wt)
}
ans := 1 // s=0 一定满足要求
f := make([][][]int, 1<<n)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, n)
for k := range f[i][j] {
f[i][j][k] = math.MaxInt / 2
}
}
}
f[0] = g
for s := uint(1); s < 1<<n; s++ {
k := bits.TrailingZeros(s)
t := s ^ (1 << k)
ok := true
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
f[s][i][j] = min(f[t][i][j], f[t][i][k]+f[t][k][j])
if ok && j < i && s>>i&1 != 0 && s>>j&1 != 0 && f[s][i][j] > maxDistance {
ok = false
}
}
}
if ok {
ans++
}
}
return ans
}
class Solution {
public int numberOfSets(int n, int maxDistance, int[][] roads) {
int[][] g = new int[n][n];
for (int[] row : g) {
Arrays.fill(row, Integer.MAX_VALUE / 2);
}
for (int[] e : roads) {
int x = e[0];
int y = e[1];
int wt = e[2];
g[x][y] = Math.min(g[x][y], wt);
g[y][x] = Math.min(g[y][x], wt);
}
int ans = 1; // s=0 一定满足要求
int[][][] f = new int[1 << n][n][n];
for (int[][] matrix : f) {
for (int[] row : matrix) {
Arrays.fill(row, Integer.MAX_VALUE / 2);
}
}
f[0] = g;
for (int s = 1; s < (1 << n); s++) {
int k = Integer.numberOfTrailingZeros(s);
int t = s ^ (1 << k);
boolean ok = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
f[s][i][j] = Math.min(f[t][i][j], f[t][i][k] + f[t][k][j]);
if (ok && j < i && (s >> i & 1) != 0 && (s >> j & 1) != 0 && f[s][i][j] > maxDistance) {
ok = false;
}
}
}
ans += ok ? 1 : 0;
}
return ans;
}
}
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
g = [[inf] * n for _ in range(n)]
for x, y, wt in roads:
g[x][y] = min(g[x][y], wt)
g[y][x] = min(g[y][x], wt)
ans = 1 # s=0 一定满足要求
f = [[[inf] * n for _ in range(n)] for _ in range(1 << n)]
f[0] = g
for s in range(1, 1 << n):
k = s.bit_length() - 1
t = s ^ (1 << k)
ok = 1
for i in range(n):
for j in range(n):
f[s][i][j] = min(f[t][i][j], f[t][i][k] + f[t][k][j]) # 手动求 min 可以更快
if ok and j < i and s >> i & 1 and s >> j & 1 and f[s][i][j] > maxDistance:
ok = 0
ans += ok
return ans
class Solution {
public int numberOfSets(int n, int maxDistance, int[][] roads) {
int[][] g = new int[n][n]; // 领接矩阵
for (int i = 0; i < n; i++) {
Arrays.fill(g[i], Integer.MAX_VALUE / 2); // 防止加法溢出
g[i][i] = 0;
}
for (int[] e : roads) {
int x = e[0], y = e[1], wt = e[2];
g[x][y] = Math.min(g[x][y], wt);
g[y][x] = Math.min(g[y][x], wt);
}
int ans = 0;
int[][] f = new int[n][n];
next:
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if ((s >> i & 1) == 1) {
System.arraycopy(g[i], 0, f[i], 0, n);
}
}
// Floyd
for (int k = 0; k < n; k++) {
if ((s >> k & 1) == 0) continue;
for (int i = 0; i < n; i++) {
if ((s >> i & 1) == 0) continue;
for (int j = 0; j < n; j++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
if ((s >> i & 1) == 0) continue;
for (int j = 0; j < n; j++) {
if ((s >> j & 1) == 1 && f[i][j] > maxDistance) {
continue next;
}
}
}
ans++;
}
return ans;
}
}
// 二进制枚举 + floyd 算法
func numberOfSets(n, maxDistance int, roads [][]int) (ans int) {
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
if j != i { // g[i][i] = 0
g[i][j] = math.MaxInt / 2 // 防止加法溢出
}
}
}
for _, e := range roads {
x, y, wt := e[0], e[1], e[2]
g[x][y] = min(g[x][y], wt)
g[y][x] = min(g[y][x], wt)
}
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
next:
for s := 0; s < 1<<n; s++ { // 枚举子集
for i, row := range g {
if s>>i&1 == 0 { continue }
copy(f[i], row)
}
// Floyd
for k := range f {
if s>>k&1 == 0 { continue }
for i := range f {
if s>>i&1 == 0 { continue }
for j := range f {
f[i][j] = min(f[i][j], f[i][k]+f[k][j])
}
}
}
for i, di := range f {
if s>>i&1 == 0 { continue }
for j, dij := range di {
if s>>j&1 > 0 && dij > maxDistance {
continue next
}
}
}
ans++
}
return
}
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
g = [[inf] * n for _ in range(n)]
for i in range(n):
g[i][i] = 0
for x, y, wt in roads:
g[x][y] = min(g[x][y], wt)
g[y][x] = min(g[y][x], wt)
f = [None] * n
def check(s: int) -> int:
for i, row in enumerate(g):
if s >> i & 1:
f[i] = row[:]
# Floyd
for k in range(n):
if (s >> k & 1) == 0: continue
for i in range(n):
if (s >> i & 1) == 0: continue
for j in range(n):
f[i][j] = min(f[i][j], f[i][k] + f[k][j])
for i, di in enumerate(f):
if (s >> i & 1) == 0: continue
for j, dij in enumerate(di):
if s >> j & 1 and dij > maxDistance:
return 0
return 1
return sum(check(s) for s in range(1 << n)) # 枚举子集
