Pythonでのロードトリップでの国際旅行の最小数を見つけるためのプログラム

さまざまな国のさまざまな都市を訪問するロードトリップを計画する必要があるとします。道路'R'のリストがあり、各要素は（x、y、cost）として記述されています。 xは道路の出発都市を示し、yは道路の目的都市を示し、costはその道路を移動するコストを示します。また、各要素が国であり、要素にその国の都市が含まれているリスト「C」もあります。これで、出発地の都市「s」と目的地の都市「e」もあり、出発地の都市から目的地の都市に移動したいと考えています。これらすべての情報を考慮して、旅行を完了するために必要な国際旅行の最小数と、旅行の総旅行費用を確認する必要があります。これら2つの値を出力として出力する必要があります。

したがって、入力がR =[[0、1、2]、[1、2、2]、[0、2、3]、[1、3、3]]、C =[[0]、 [1]、[2、3]]、s =0、e =3の場合、出力は（2,5）になります。

したがって、0から3に移動するには、パス0->1->3を使用します。この道をたどる道は[0、1、2]と[1、3、3]です。したがって、国から国への総移動量は2であり、総コストは2 + 3=5です。

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

• cont：=デフォルト値が0の新しいマップ
• 各インデックスidx、およびCの要素アイテムに対して
  • アイテムのkごとに、
    • cont [k]：=idx
• adj_list：=値としてリストを含む新しいマップ
• Rのa、b、wtごとに、
  • cont[a]がcont[b]と同じでない場合、
    • wt：=wt​​ + 10 ^ 10
  • adj_list [a]の最後にペア（b、wt）を挿入します
• distance：=デフォルト値が10^20である新しいマップ
• 距離[s]：=0
• 訪問：=新しいセット
• t：=ペア（0、s）を含む新しいヒープ
• tが空でない間は、
  • pair（d、c）：=ヒープから最小のアイテムをポップします
  • 訪問者にcが存在する場合、
    • 次の反復に進む
  • 訪問先にcを追加
  • adj_list [c]のj、wtごとに、do
    • distance [j]> d + wtの場合、
      • 距離[j]：=d + wt
      • ヒープtにペア（d + wt、j）を挿入します
• リターンペア（（distance [e] / 10 ^ 10）のフロア値、（distance [e] mod 10 ^ 10））

例

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
from heapq import heappush, heappop

def solve(R, C, s, e):
   cont = defaultdict(int)
   for idx, item in enumerate(C):
      for k in item:
         cont[k] = idx

   adj_list = defaultdict(list)
   for a, b, wt in R:
      if cont[a] != cont[b]:
         wt += 10 ** 10
      adj_list[a].append((b, wt))

   distance = defaultdict(lambda: 10 ** 20)
   distance[s] = 0
   visited = set()

   t = [(0, s)]
   while t:
      d, c = heappop(t)
      if c in visited:
         continue
      visited.add(c)
      for j, wt in adj_list[c]:
         if distance[j] > d + wt:
            distance[j] = d + wt
            heappush(t, (d + wt, j))

   return distance[e] // 10 ** 10, distance[e] % 10 ** 10

print(solve([[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3))

入力

[[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3

出力

(2, 5)