Python中查找市民进入市场的最小成本的程序

假设有n个城市和m条连接城市的道路。人们需要市场来购买商品。现在，在城市中没有市场，城市之间的道路正在施工中。如果（i）该城市包含市场; （ii）经过市场之处有道路连接城市，则可以在两个城市之间建造双向道路。建造道路的成本为x，建造市场的成本为y，我们必须找出提供市场接入的最小成本。

城市数组’cities’包含有关城市的信息，指定哪些城市可以通过道路连接。

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

我们将遵循以下步骤-

如果x小于等于y，则返回n * x。
否则
- adj_list: 一个包含列表元素的地图
- 对于每个城市，执行以下操作：
  - city1：city [0]
  - city2：city [1]
  - 将city2插入adj_list [city1]的末尾
  - 将城市1插入adj_list [city2]的末尾
- temp：一个新的大小为（n + 1）的列表，初始化值为True
- 值：0
- dq：双端队列
- 对于范围为1到n + 1的cur，执行以下操作：
  - 如果temp [cur]为非零，则：
  - 值：值+x
  - 将cur插入dq的最右端
  - temp [cur]：False
  - 当dq不为空时执行以下操作：
  - 对于每个i adj_list [提取的dq最左元素]，执行以下操作：
  - 如果temp [i]为非零，则：
    - 将i插入dq的最右端
    - temp [i]：False
    - 值：值+y
- 返回值

例子

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