1. 解题思路
这一题虽然是一个hard的题目,不过其实思路上也并不难,由于最多只有10个节点,因此,我们可以直接考察全部的至多 2 10 2^{10} 210种组合,考察每一种情况下的子图是否满足条件即可。
而对于每一个具体的子图,事实上就是一个求图中任意两点间最小距离的问题,这个是个典型的图问题,用Floyd算法就可以直接得到答案了。
不过比较尴尬的是,虽然我知道有算法可以直接干这个事,不过具体的Floyd算法和DijkStra算法已经基本忘干净,最后还是网上找了个现成的code完成的,就很坑爹……
后面花点时间单独重新整理一下这俩算法吧……
2. 代码实现
给出python代码实现如下:
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
roads = sorted(roads, key=lambda x: x[-1])
valid_roads = []
seen = set()
for u, v, w in roads:
if (u, v) in seen:
continue
if w > maxDistance:
break
valid_roads.append((u, v, w))
seen.add((u, v))
seen.add((v, u))
@lru_cache(None)
def get_min_distance(status):
distances = [[0 if i == j else math.inf for i in range(n)] for j in range(n)]
for u, v, w in valid_roads:
if ((status >> u) & 1) & ((status >> v) & 1):
distances[u][v] = distances[v][u] = w
for o in range(n):
for u in range(n):
for v in range(n):
distances[u][v] = min(distances[u][o] + distances[o][v], distances[u][v])
distances[v][u] = min(distances[u][o] + distances[o][v], distances[v][u])
return distances
@lru_cache(None)
def dfs(idx, status):
if idx == n:
distances = get_min_distance(status)
return 1 if all(distances[u][v] <= maxDistance for u in range(n) for v in range(u+1, n) if ((status >> u) & 1) & ((status >> v) & 1)) else 0
return dfs(idx+1, status) + dfs(idx+1, status | (1 << idx))
return dfs(0, 0)
提交代码评测得到:耗时8546ms,占用内存53.1MB。