用 Python 编写程序，找出让市民进入市场所需的最低成本

pythonserver side programmingprogramming更新于 2026/1/30 13:00:17

假设有 n 个城市，m 条道路连接这些城市。市民需要市场来购买商品。现在，城市中没有市场，城市之间的道路正在修建中。如果 (i) 城市包含市场；(ii) 可以通过有市场的道路访问城市，则可以在两个城市之间修建一条双向道路。修建道路的成本为 x，修建市场的成本为 y，并且它们是给定的。我们必须找出让每个城市的市民进入市场的最低成本。数组"cities"包含有关哪些城市可以通过道路连接的信息。

因此，如果输入为 n = 4、m = 3、x = 1、y = 2、城市 = [[1, 2], [2, 3], [3, 4]]，则输出将为 4。

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

为了解决这个问题，我们将遵循以下步骤 −

如果 x <= y，则
- 返回 n * x
否则，
- adj_list := 包含列表作为元素的映射
- 对于 cities 中的每个城市，执行
  - city1 := city[0]
  - city2 := city[1]
  - 在 adj_list[city1] 末尾插入 city2
  - 在 adj_list[city2] 末尾插入 city1
- temp := 一个大小为 (n + 1) 的新列表，初始化值为 True
- value := 0
- dq := 一个双端队列
- 对于范围为 1 到 n + 1 的 cur，执行
  - 如果 temp[cur] 非零，则
    - value := value + x
    - 将 cur 插入 dq 的最右端
    - temp[cur] := False
    - 当 dq 不为空时，执行
    - 对于每个 i adj_list[提取的 dq 最左边元素]，执行
      - 如果 temp[i] 非零，则
        
        将 i 插入 dq 的最右端
        
        temp[i] := False
        
        value := value + y
- 返回 value

示例

让我们看看下面的实现以便更好地理解 −

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]]))