问题描述 链接到标题

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

解题思路 链接到标题

方法一:状态压缩+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表示更新后的状态二进制数。

代码 链接到标题 

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;
    }
};