1
class Solution:
2
    def shortestPathLength(self, graph: List[List[int]]) -> int:
3
        n = len(graph)
4
        dist = [[inf] * n for _ in range(n)]
5

6
        for i, x in enumerate(graph):
7
            dist[i][i] = 0
8
            for ii in x:
9
                dist[i][ii] = 1
10

11
        # floyd-warshall
12
        for k in range(n):
13
            for i in range(n):
14
                for j in range(n):
15
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
16

17
        @cache
18
        def fn(x, mask):
19
            if mask == 0:
20
                return 0
21
            ans = inf
22
            for i in range(n):
23
                if mask & (1 << i):
24
                    ans = min(ans, dist[x][i] + fn(i, mask ^ (1 << i)))
25
            return ans
26

27
        return min(fn(x, (1 << n) - 1) for x in range(n))