LC847: Shortest Path Visiting All Nodes

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int ed = (1<<n)-1;

        vector<vector<int>> vis(ed+1, vector<int>(n, 2e9));
        queue<pair<int, pair<int, int>>> q; // d k u

        vis[1][0] = 0;
        q.push({0, {1, 0}});

        for(int i=1;i<n;++i){
            if(graph[i].size() > 1) continue;
            vis[1<<i][i] = 0;
            q.push({0, {1<<i, i}});
        }

        while(!q.empty()){
            int d = q.front().first;
            int k = q.front().second.first;
            int u = q.front().second.second;
            q.pop();

            if(k == ed) return d;

            for(auto v:graph[u]){
                if(vis[k|(1<<v)][v] != 2e9) continue;
                vis[k|(1<<v)][v] = d+1;
                q.push({d+1, {k|(1<<v), v}});
            }
        }

        return -1; // impossible
    }
};