You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

&nbsp;
Example 1:

Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]


Example 2:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]


&nbsp;
Constraints:


	n == graph.length
	1 &lt;= n &lt;= 12
	0 &lt;= graph[i].length &lt;&nbsp;n
	graph[i] does not contain i.
	If graph[a] contains b, then graph[b] contains a.
	The input graph is always connected.


class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        dist = [[inf]*n for _ in range(n)]
        
        for i, x in enumerate(graph): 
            dist[i][i] = 0
            for ii in x: dist[i][ii] = 1
        
        # floyd-warshall 
        for k in range(n): 
            for i in range(n): 
                for j in range(n): 
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        @cache 
        def fn(x, mask): 
            if mask == 0: return 0 
            ans = inf 
            for i in range(n): 
                if mask & (1 << i): 
                    ans = min(ans, dist[x][i] + fn(i, mask ^ (1<<i)))
            return ans 
        
        return min(fn(x, (1 << n)-1) for x in range(n))
class Solution {
    class Pair {
        int i;
        int path;
        public Pair(int i, int path) {
            this.i = i;
            this.path = path;
        }
    }
    public int shortestPathLength(int[][] graph) {
        /*
        For each node currentNode, steps as key, visited as value
        boolean[currentNode][steps]
        */
        int n = graph.length;

        // 111....1, 1<< n - 1
        int allVisited = (1 << n) - 1;

        boolean[][] visited = new boolean[n][1 << n];
        Queue<Pair> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (1 << i == allVisited) return 0;
            visited[i][1 << i] = true;
            q.offer(new Pair(i, 1 << i));
        }
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Pair p = q.poll();
                int[] edges = graph[p.i];

                for(int t: edges) {
                    int path = p.path | (1 << t);
                    if (path == allVisited) return step + 1;
                    if (!visited[t][path]) {
                        visited[t][path] = true;
                        q.offer(new Pair(t, path));
                    }
                }
            }
            step++;
        }
        return step;
    }
}
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        string mask = "";
        string eq = "";
        for(int i=0; i<n; i++){
            mask += '0';
            eq += '1';
        }
        queue<pair<int,string>>q;
        set<pair<int,string>>s;
        for(int i=0; i<n; i++){
            string temp = mask;
            temp[i] = '1';
            q.push({i,temp});
            s.insert({i,temp});
        }
        int c = 0;
        int flag = 0;
        while(!q.empty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                auto top = q.front();
                q.pop();
                if(top.second == eq) return c;
                for(auto p: graph[top.first]){
                    string temp1 = top.second;
                    temp1[p] = '1';
                    if(s.count({p,temp1}) == 0){
                        q.push({p,temp1});
                        s.insert({p,temp1});
                    }
                }
            }
            c++;
            cout<<"c is "<<c;
        }
        return -1;
    }
};
/**
 * @param {number[][]} graph
 * @return {number}
 */
var shortestPathLength = function(graph) {
    const n = graph.length;
    const allVisited = (1 << n) - 1;
    const queue = [];
    const visited = new Set();

    for (let i = 0; i < n; i++) {
        queue.push([1 << i, i, 0]);
        visited.add((1 << i) * 16 + i);
    }

    while (queue.length > 0) {
        const [mask, node, dist] = queue.shift();

        if (mask === allVisited) {
            return dist;
        }

        for (const neighbor of graph[node]) {
            const newMask = mask | (1 << neighbor);
            const hashValue = newMask * 16 + neighbor;

            if (!visited.has(hashValue)) {
                visited.add(hashValue);
                queue.push([newMask, neighbor, dist + 1]);
            }
        }
    }

    return -1;
}
Shortest Path Visiting All Nodes