被裁当天得知自己怀孕了，HR知道后，立马将我从裁员名单中去除，本来都要被裁了，现在却留下来，是不是应该感谢宝宝。

这宝宝还没出生，已经开始帮妈妈保住饭碗了？

事情也挺魔幻的。网友本来已经进裁员名单了，估计心里都准备收拾东西走人了，结果当天发现自己怀孕。HR一知道，态度立马变了，裁员名单里直接把她划掉。

你说这事该不该感谢宝宝，当然可以感谢，毕竟这时间点太巧了，跟开了个职场免死金牌似的。但往细了想，也挺让人不是滋味。公司不是突然良心发现，是知道这个阶段裁孕妇风险太高，怕惹麻烦，怕赔钱，怕后面扯不清。

所以宝宝确实是“救场”了，但真正离谱的是，一个人能不能留下来，最后居然靠的是这种偶然。打工人平时加班、绩效、项目，全都不一定稳，反倒是HR听到怀孕俩字，手速比删库还快。

图里节点不多，但你要是按普通最短路去跑，很快就会绕晕。

这个题最容易写错的地方，不是 BFS，而是“走到同一个节点”这件事根本不够描述当前状态。

比如你现在到了 3 号节点。

一种情况是你已经访问过 0、1、2、3。

另一种情况是你只访问过 3。

这两个状态后面能走出来的答案完全不一样。你要是只用 visited[node] 去判重，基本就废了。我第一眼看这题，先不会想 Dijkstra，边权都是 1，直接 BFS。关键是把“当前在哪个点”和“已经访问了哪些点”绑在一起。

状态长这样：

(node, mask)

node 表示当前停在哪个节点。

mask 用二进制表示访问过哪些节点。

比如一共 4 个点，mask = 0b1011，意思就是访问过 0、1、3，还没访问 2。

目标也很直接：

target = (1 << n) - 1

也就是所有节点对应的二进制位都变成 1。

代码可以这么写：

from collections import deque
from typing import List

classSolution:
defshortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
if n <= 1:
return0

        full = (1 << n) - 1
        queue = deque()
        seen = set()

for start in range(n):
            state = (start, 1 << start)
            queue.append((start, 1 << start, 0))
            seen.add(state)

while queue:
            cur, mask, step = queue.popleft()

for nxt in graph[cur]:
                next_mask = mask | (1 << nxt)

if next_mask == full:
return step + 1

                next_state = (nxt, next_mask)
if next_state in seen:
continue

                seen.add(next_state)
                queue.append((nxt, next_mask, step + 1))

return0

这里有个小细节，BFS 不是从某一个节点开始，而是所有节点一起入队。

为什么？

因为题目没规定起点。你可以从任意节点出发，那就别傻乎乎枚举每个起点跑一遍 BFS。把每个节点都当成初始状态塞进队列，本质上就是多源 BFS，谁先走到全访问状态，谁就是最短路径。

这题还有一个容易误判的点：节点可以重复访问。

很多人看到“访问所有节点”，下意识以为每个节点只能走一次。不是。这个题求的是最短路径长度，不是哈密顿路径。图可能长得很别扭，中间节点来回踩几次很正常。

比如：

graph = [[1], [0, 2, 4], [1, 3], [2], [1]]

从左边走到右边，再回来拐到另一个分支，中间的 1 肯定会重复经过。这个重复不是问题，问题是同一个 (node, mask) 没必要重复进队。

我一般判断这题能不能用状态压缩，就看两个东西。

第一，节点数量小。

第二，某个状态能用二进制很干净地表示。

这题刚好都满足。n 个节点，mask 最多 2^n 种，每种状态还要乘上当前节点，所以状态数量大概是：

n * 2^n

BFS 每次再扫一遍相邻边，复杂度能接受。

这段代码里真正值钱的不是那几行位运算，而是判重方式：

seen.add((nxt, next_mask))

不是只看 nxt。

只看当前节点，信息丢了。

只看访问集合，也不够，因为你停在不同节点，下一步能走的边也不一样。

两个条件合在一起，状态才完整。这个点想明白了，这题就没什么花活了。