Untitled

mail@pastecode.io avatar
unknown
python
7 months ago
714 B
17
Indexable
Never
class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        n = len(graph)
        fullMask = (1 << n) - 1
        seenMasks = set()

        @cache
        def dp(node, mask):
            state = (node, mask)

            if mask == fullMask:
                return 0

            
            seenMasks.add(state)

            resForThis = float('inf')
            for adj in graph[node]:
                newMask = mask | (1 << adj)
                if (adj, newMask) not in seenMasks:
                    resForThis = min(resForThis, 1 + dp(adj, newMask))
            seenMasks.remove(state)
            return resForThis

        return min(dp(node, 1 << node) for node in range(n))
Leave a Comment