847. Shortest Path Visiting All Nodes

Tag: State Compression, BFS, No AC first time

Description

Solutions

We can see from constrains that n<=12, so we can use state compression. Also, the weight of each edge is 1, which reminds us of BFS to search for the lowest distance to reach final state 1<<n - 1

Some tricky points

• Use tuple to store a three tuple, {node, mask, dist} for the current node, mask and current distance.
• Use a array or map to store the visited state, states should be distinct by their mask and current node.

Code

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        queue<tuple<int,int,int>> q;
        //{node, mask, dist}
        vector<vector<int>> seen(n, vector<int>(1 << n, 0));
        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 [u, mask, dist] = q.front();
            q.pop();
            if(mask == (1 << n) - 1){
                ans = dist;
                break;
            }
			//search adjecent nodes
            for(auto next : graph[u]){
                int nxtMask = mask | 1 << next;
                if(!seen[next][nxtMask]){
                    q.emplace(next, nxtMask, dist+1);
                    seen[next][nxtMask] = true;
                }
            }
        }
        return ans;
    }
};