Участник:Бушенкова Ксения/LeetCode Shortest Path visiting all nodes

Материал из DISCOPAL
Перейти к: навигация, поиск

Бушенкова Ксения 11:55, 26 мая 2020 (MSK) https://leetcode.com/problems/shortest-path-visiting-all-nodes/


class Solution(object):
    def shortestPathLength(self, graph):
        N = len(graph)
        queue = collections.deque((1 << x, x) for x in xrange(N))
        dist = collections.defaultdict(lambda: N*N)
        for x in xrange(N): dist[1 << x, x] = 0
 
        while queue:
            cover, head = queue.popleft()
            d = dist[cover, head]
            if cover == 2**N - 1: return d
            for child in graph[head]:
                cover2 = cover | (1 << child)
                if d + 1 < dist[cover2, child]:
                    dist[cover2, child] = d + 1
                    queue.append((cover2, child))