847. Shortest Path Visiting All Nodes

Tags:

• Hard
• bfs
• bitmask
• recommend
• practice
• TBD

Link

Can't understand dfs now

BFS

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:

        N = len(graph)

        dq = deque([(0, i, 1 << i) for i in range(N)])

        S = set()

        while dq:

            step, i, state = dq.popleft()

            if state == (1 << N) - 1:
                return step

            if (i, state) in S:
                continue

            S.add((i, state))


            for ii in graph[i]:
                dq.append((step+1, ii, state | 1 << ii))

        return 0

dfs