847.shortest path visiting all nodes

Description Link to heading

Solution Link to heading

solution 1: bitmask + bfs Link to heading

For example, $(0101)_2$ means the nodes numbered 0 and 2 have been accessed, while nodes nubmered 1 and 3 have not been accessed.

bfs;

Array seen[x][mask_x] means whether node x and path mask_x have been accessed.

Code Link to heading

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); // idx,bitmask,dist
            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;
            }
            // search nodes adjacent to the current node
            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;
    }
};