Manjusaka

09-17 leetcode-0847

链接 847. Shortest Path Visiting All Nodes

题目

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.

题解

这题其实直接搜索就可以，用 bitmap 记录访问过的节点，然后如果邻居节点已经访问过，则有两种可能

1. 直接从本节点访问邻居节点
2. 改变本节点状态，获取访问邻居节点的最短路径

然后求最小值

class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        cache = {}
        special_mask = (1 << len(graph)) - 1

        def search(node: int, mask: int) -> int:
            if (node, mask) in cache:
                return cache[(node, mask)]
            if mask & (mask - 1) == 0:
                return 0
            cache[(node, mask)] = 1000000
            for next_node in graph[node]:
                if mask & (1 << next_node):
                    visited = search(next_node, mask)
                    non_visited = search(next_node, mask ^ (1 << node))
                    cache[(node, mask)] = min(cache[(node, mask)], min(visited, non_visited) + 1)
            return cache[(node, mask)]

        return min(search(i, special_mask) for i in range(len(graph)))

这题也还能直接暴力 bitmap + bfs 来做

class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        length = len(graph)
        queue = deque((i, 1 << i, 0) for i in range(length))
        visited = {(i, 1 << i) for i in range(length)}
        while queue:
            node, mask, distance = queue.popleft()
            if mask == (1 << length) - 1:
                return distance
            for next_node in graph[node]:
                next_mask = mask | (1 << next_node)
                if (next_node, next_mask) not in visited:
                    queue.append((next_node, next_mask, distance + 1))
                    visited.add((next_node, next_mask))
        return 0