# 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 作为答案


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://851958789.gitbook.io/notes/0847_shortest_path_visiting_all_nodes/slt.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.