2959.关闭分部的可行集合数目

链接：2959.关闭分部的可行集合数目
难度：Hard
标签：位运算、图、枚举、最短路、堆（优先队列）
简介：请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

题解 1 - python

• 编辑时间：2024-07-17
• 执行用时：1863ms
• 内存消耗：16.52MB
• 编程语言：python
• 解法介绍：枚举所有可能，用短路算法求出两地之间的最短路径。

class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        def check(mask: int) -> int:
            d = [[inf for _ in range(n)] for _ in range(n)]
            for n1, n2, w in roads: d[n1][n2] = d[n2][n1] = min(d[n1][n2], d[n2][n1], w)
            for k in range(n):
                if mask & (1 << k):
                    for i in range(n):
                        if mask & (1 << k):
                            for j in range(n):
                                if mask & (1 << j):
                                    d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
            for i in range(n):
                if mask & (1 << i):
                    for j in range(i):
                        if mask & (1 << j):
                            if d[i][j] > maxDistance:
                                return False
            return True
        return sum(check(i) for i in range(2 ** n))