> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0847_shortest_path_visiting_all_nodes/slt.md).

# Solution1 BFS

* 时间复杂度 O((n ^ 2) \* (2 ^ n))

    常规的 BFS 时间复杂度是 O(n + m) n 是节点数，m 是边数。

    本题引入 mask 其最大值是 2 ^ n。可以看做是进行了 2 ^ n 次常规 BFS

    本题 m 没有显示给出，考虑最坏情况下的完全图 有 n^2 条边。
* 空间复杂度 O(n \* (2 ^ n))

    即 que 占得空间

由于点可以重复访问，我们使用三元组 (u,mask,dist) 表示队列中的每一个元素

* u 当前节点编号
* mask 一个长度为 n 的二进制数，表示每一个节点是否经过。第 i 位为 1，表示 i 经过过
* dist 表示到当前节点为止所经过的路径长度

visited 数组中也不同于常规的 BFS 只保存访问过的节点，还要保存节点对应的 mask 状态

在搜索的过程中，如果当前三元组中的 mask 包含 n 个 1（即 mask=2^n-1 那么我们就可以返回 dist 作为答案