市民がPythonの市場にアクセスできるようにするための最小コストを見つけるためのプログラム

n個の都市とm個の都市を結ぶ道路があるとします。人々の市民は彼らが彼らの商品を買うことができる市場を必要としています。現在、都市には市場がなく、都市間の道路が建設中です。次の場合、2つの都市間に双方向道路を建設できます。（i）都市に市場が含まれている。 （ii）市場がある道路で都市を訪れることができます。道路を建設する費用はxであり、市場を建設する費用はyであり、それらは与えられます。各都市の市民に市場へのアクセスを提供するための最小コストを見つける必要があります。配列「cities」には、道路で接続できる都市に関する情報が含まれています。

したがって、入力がn =4、m =3、x =1、y =2、citys =[[1、2]、[2、3]、[3、4]]の場合、出力は次のようになります。 4.

ここでは、4つの都市1、2、3、4を見ることができます。市場が都市1に建設され、（1、4）と（1,3）の間にさらに2つの道路が建設された場合、合計コストは2+1になります。 +1=4。これが最小コストです。

これを解決するには、次の手順に従います-

• x <=yの場合、
  • return n * x
• それ以外の場合、
  • adj_list：=要素としてリストを含むマップ
  • 都市内の各都市について、
    • city1：=city [0]
    • city2：=city [1]
    • adj_list [city1]
    の最後にcity2を挿入します
    • adj_list [city2]
    の最後にcity1を挿入します
  • temp：=値Trueで初期化されたサイズ（n + 1）の新しいリスト
  • 値：=0
  • dq：=両端キュー
  • 1からn+1の範囲のcurの場合、do
    • temp [cur]がゼロ以外の場合、
      • 値：=値+ x
      • dqの右端にcurを挿入します
      • temp [cur]：=False
      • dqが空ではない場合は、実行してください
      • i adj_list [dqの左端の要素を抽出]ごとに、
        を実行します。
        • temp [i]がゼロ以外の場合、
          • dqの右端にiを挿入
          • 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]]))

入力

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

出力

4