Skip to content

Latest commit

 

History

History
168 lines (106 loc) · 7.35 KB

3108.minimum-cost-walk-in-weighted-graph.md

File metadata and controls

168 lines (106 loc) · 7.35 KB
Raw

题目地址(3108. 带权图里旅途的最小代价 - 力扣（LeetCode）)

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

题目描述

给你一个 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：

输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]

输出：[1,-1]

解释：

第一个查询想要得到代价为 1 的旅途，我们依次访问：0->1（边权为 7 ）1->2 （边权为 1 ）2->1（边权为 1 ）1->3 （边权为 7 ）。

第二个查询中，无法从节点 3 到节点 4 ，所以答案为 -1 。

示例 2：

输入：n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]

输出：[0]

解释：

第一个查询想要得到代价为 0 的旅途，我们依次访问：1->2（边权为 1 ），2->1（边权 为 6 ），1->2（边权为 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

前置知识

公司

  • 暂无

思路

由于代价是按位与 ，而不是相加，因此如果 s 到 t 我们尽可能多的走，那么 and 的值就会越来越小。这是因为两个数的与一定不比这两个数大。

  • 考虑如果 s 不能到达 t，那么直接返回 -1。
  • 如果 s 到 t 可以到达，说明 s 和 t 在同一个联通集。对于联通集外的点，我们无法到达。而对于联通集内的点，我们可以到达。前面说了，我们尽可能多的做，因此对于联通集内的点，我们都走一遍。答案就是联通集合中的边的 and 值。

使用并查集模板可以解决，主要改动点在于 union 方法。大家可以对照我的并查集标准模板看看有什么不同。

关键点

代码

  • 语言支持：Python3

Python3 Code:

class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      self.all_and = {}
      # 初始化 parent，size 和 cnt
      # Initialize parent, size and cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1
          self.all_and[i] = 2 ** 30 - 1 # 也可以初始化为 -1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q, w):
    #   if self.connected(p, q): return # 这道题对于联通的情况不能直接 return，具体可以参考示例 2. 环的存在
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      # p 连通块的 and 值为 w1，q 连通块的 and 值为 w2，合并后就是 w1 & w2 & w
      self.all_and[leader_p] = self.all_and[leader_q] = self.all_and[leader_p] & w & self.all_and[leader_q]
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)
        
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        uf = UF(n)
        for x, y, w in edges:
            g[x].append((y, w))
            g[y].append((x, w))
            uf.union(x, y, w)

        ans = []
        for s, t in query:
            if not uf.connected(s, t):
                ans.append(-1)
            else:
                ans.append(uf.all_and[uf.parent[s]])
        return ans

复杂度分析

令 m 为 edges 长度。

  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(m + n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。