847.md

847. Shortest Path Visiting All Nodes

Solution 1 (time O(m2^n), space O(n2^n))

# BFS
class Solution(object):
    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        n = len(graph)
        queue = [(i, 1 << i, 0) for i in range(n)]
        visited = {(i, 1 << i) for i in range(n)}
        ans = 0
        while queue:
            cur_node, cur_state, cur_dist = queue.pop(0)
            if cur_state == (1 << n) - 1:
                ans = cur_dist
                break
            for new_node in graph[cur_node]:
                new_state = cur_state | (1 << new_node)
                if (new_node, new_state) not in visited:
                    visited.add((new_node, new_state))
                    queue.append((new_node, new_state, cur_dist + 1))
        return ans