LC 3108. 带权图里旅途的最小代价

https://leetcode.cn/problems/minimum-cost-walk-in-weighted-graph/description/

这题挺有意思的，需要稍微想想来简化问题。

假设在一个连通图里面，存在A->B->C路径的话，到了C之后某些bit消失了。那么其实我们可以按照C->B->A返回来，这样的话从A起始的时候这个bit就消失了。
也就是说，如果在C点上bit消失了，那么在A点上bit也可以消失。
也就是说，在一个连通图里面，任何两点的最短距离其实是一个固定的值
这个固定的值是将整个连通图里面的所有weight进行AND，否则的话我们可以不断地尝试将bit unset掉。

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        cut = [-1] * n
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))

        def dfs(x, c):
            cut[x] = c
            value = 0xffffffff
            for y, w in adj[x]:
                value &= w
                if cut[y] != -1: continue
                value &= dfs(y, c)
            return value

        c = 0
        values = []
        for i in range(n):
            if cut[i] != -1: continue
            value = dfs(i, c)
            values.append(value)
            c += 1

        ans = []
        for x, y in query:
            if cut[x] == cut[y]:
                ans.append(values[cut[x]])
            else:
                ans.append(-1)
        return ans