3108：带权图里旅途的最小代价（2108 分）

力扣第 392 场周赛第 4 题

题目

给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。

给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。

在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。

如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, ..., wk ，那么代价为w0 & w1 & w2 & ... & wk ，其中 & 表示按位与 AND 操作。

给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -1 。

返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。

示例 1：

提示：

• 1 <= n <= 105
• 0 <= edges.length <= 105
• edges[i].length == 3
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= wi <= 105
• 1 <= query.length <= 105
• query[i].length == 2
• 0 <= si, ti <= n - 1

分析

典型的并查集，求出每个连通块的最小代价即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        def find(x):
            if f[x]!=x:
                f[x] = find(f[x])
            return f[x]

        def union(x,y):
            f[find(x)] = find(y)

        f = list(range(n))
        for u,v,w in edges:
            union(u,v)
        g = {}
        for u,v,w in edges:
            g[find(u)] = g.get(find(u),w)&w
        return [0 if s==t else g[find(s)] if find(s)==find(t) else -1 for s,t in query]

210 ms