找出最小成本的程序，以便公民可以进入 Python 市场

• Z时代
• 2024-01-10
• 分类：综合

假设有 n 个城市和连接城市的 m 条道路。人民的公民需要可以购买商品的市场。现在，城市中没有市场，城市之间的道路是construction.A双向的，如果(i)城市有市场，两个城市之间可以建设；(ii) 城市可以通过有市场的道路访问。修建一条道路的成本是 x，建造一个市场的成本是 y，它们是给定的。我们必须找出为每个城市的公民提供市场准入的最低成本。数组“城市”包含有关哪些城市可以通过公路连接的城市的信息。

所以，如果输入像 n = 4, m = 3, x = 1, y = 2, city = [[1, 2], [2, 3], [3, 4]]，那么输出将是4.

在这里，我们可以看到 1、2、3 和 4 四个城市。如果在城市 1 建一个市场，并且在 (1, 4) 和 (1,3) 之间再建两条道路，总成本将为 2 + 1 + 1 = 4。这是最低成本。

示例

让我们看看以下实现以更好地理解 -

from collections import defaultdict, deque
def solve(n, m, x, y, cities):
   if x <= y:
      return n * x
   else:
      adj_list = defaultdict(list)
      for city in cities:
         city1 = city[0]
         city2 = city[1]
         adj_list[city1].append(city2)
         adj_list[city2].append(city1)
      temp = [True] * (n + 1)
      value = 0
      dq = deque()
      for cur in range(1, n + 1):
         if temp[cur]:
            value += x
            dq.append(cur)
            temp[cur] = False
            while dq:
               for i in adj_list[dq.popleft()]:
                  if temp[i]:
                     dq.append(i)
                     temp[i] = False
                     value += y
      return value
print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))

输入

4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]

4

以上是 找出最小成本的程序，以便公民可以进入 Python 市场 的全部内容， 来源链接： utcz.com/z/363270.html