class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
q = deque((i, 1 << i, 0) for i in range(n))
seen = {(i, 1 << i) for i in range(n)}
ans = 0
while q:
u, mask, dist = q.popleft()
if mask == (1 << n) - 1:
ans = dist
break
# 搜索相邻的节点
for v in graph[u]:
# 将 mask 的第 v 位置为 1
mask_v = mask | (1 << v)
if (v, mask_v) not in seen:
q.append((v, mask_v, dist + 1))
seen.add((v, mask_v))
return ans
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
n = len(graph)
d = [[n + 1] * n for _ in range(n)]
for i in range(n):
for j in graph[i]:
d[i][j] = 1
# 使用 floyd 算法预处理出所有点对之间的最短路径长度
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
f = [[float("inf")] * (1 << n) for _ in range(n)]
for mask in range(1, 1 << n):
# 如果 mask 只包含一个 1，即 mask 是 2 的幂
if (mask & (mask - 1)) == 0:
u = bin(mask).count("0") - 1
f[u][mask] = 0
else:
for u in range(n):
if mask & (1 << u):
for v in range(n):
if (mask & (1 << v)) and u != v:
f[u][mask] = min(f[u][mask], f[v][mask ^ (1 << u)] + d[v][u])
ans = min(f[u][(1 << n) - 1] for u in range(n))
return ans
