Участник:Бушенкова Ксения/LeetCode Shortest Path visiting all nodes — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 5: Строка 5:
 
<code-python>
 
<code-python>
 
class Solution(object):
 
class Solution(object):
     def shortestPath(self, graph):
+
     def shortestPathLength(self, graph):
 
         N = len(graph)
 
         N = len(graph)
 
         queue = collections.deque((1 << x, x) for x in xrange(N))
 
         queue = collections.deque((1 << x, x) for x in xrange(N))
Строка 19: Строка 19:
 
                 if d + 1 < dist[cover2, child]:
 
                 if d + 1 < dist[cover2, child]:
 
                     dist[cover2, child] = d + 1
 
                     dist[cover2, child] = d + 1
                     queue.append((cover2, chil
+
                     queue.append((cover2, child))
 
</code-python>
 
</code-python>

Текущая версия на 08:58, 26 мая 2020

Бушенкова Ксения 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))