Untitled

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

        @cache
        def dp(node, mask):
            mask |= 1 << node

            if mask == fullMask:
                return 0

            
            resForThis = float('inf')
            for adj in graph[node]:
                if mask & (1 << adj): continue
                resForThis = min(resForThis, 1 + dp(adj, mask))
            return resForThis

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