# 847.访问所有节点的最短路径

## 问题描述
[847.访问所有节点的最短路径](https://leetcode.cn/problems/shortest-path-visiting-all-nodes/)

## 解题思路
### 方法一:状态压缩+bfs
#### 状态压缩
由于本题中，n只有12，且状态只有访问和未访问两种，因此可以使用二进制表示法，利用`int`的低12位来代指点是否被访问过;

例如$(000...0101)_2$表示编号为0和编号为2的节点已经被访问过，而编号为1和3的节点还没有被访问过;

假设`mask`存放了当前一系列点的访问状态，假如要检查编号为`x`的点是否被访问过，可以使用位运算`a = (mask >> x) & 1`来检查，如果`a`为1，那么访问过，为0表示未访问;

假设如果表示在`x`未被访问的情况下，要去访问`x`，那么`mask_v = mask | (1 << x)`，其中`mask_v`表示更新后的状态二进制数。

## 代码
```cpp
class Solution {
  public:
    int shortestPathLength(vector<vector<int>> &graph) {
        int n = graph.size();
        queue<tuple<int, int, int>> q;
        vector<vector<int>> seen(n, vector<int>(1 << n));
        for (int i = 0; i < n; i++) {
            q.emplace(i, 1 << i, 0); // 索引、二进制掩码、距离
            seen[i][1 << i] = 1;
        }
        int ans = 0;
        while (!q.empty()) {
            auto [idx, mask, dist] = q.front();
            q.pop();
            if (mask == (1 << n) - 1) { // 2^n - 1
                ans = dist;
                break;
            }
            // 搜索当前idx相邻的节点
            for (int x : graph[idx]) {
                int mask_x = mask | (1 << x);
                if (!seen[x][mask_x]) {
                    q.emplace(x, mask_x, dist + 1);
                    seen[x][mask_x] = 1;
                }
            }
        }
        return ans;
    }
};
```