Pythonで最終目標に到達するために必要なバスの最小数を見つけるためのプログラム

各行に3つのフィールド[src、dest、id]が含まれるn x 3マトリックスがあるとします。これは、バスがsrcからdestへのルートを持っていることを意味します。新しいバスに乗るには1単位のお金がかかりますが、同じバスにとどまる場合は1単位だけ支払う必要があります。場所0から最終停留所（最大の場所）までバスに乗るのに必要な最小費用を見つける必要があります。解決策がない場合は-1を返します。

したがって、入力が次のような場合

次に、出力は2になります。これは、場所0で0を取得し、場所3で降りることができるためです。次に、バス1に乗って場所5に到達します。

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

• start：=0
• target：=指定された行列の最大の場所
• adj：=空のマップ
• 接続内のsrc、dest、idごとに、
  • adj [src]の最後に（dest、id）を挿入します
• hp：=アイテム（0、開始、-1）のヒープ
• 見た：=空の地図
• hpが空でない間は、
  • （cost、cur_pos、cur_bus）：=ヒープhpの最上位要素、およびhpからtopを削除
  • cur_posがtargetと同じ場合、
    • 返品費用
  • cur_busがseen[cur_pos]にある場合、
    • 次の反復に進む
  • cur_busをseen[cur_pos]に挿入します
  • adj [cur_pos]の各（nex_pos、nex_bus）に対して、
    を実行します。
    • next_cost：=コスト
    • nex_busがcur_busと同じでない場合、
      • next_cost：=next_cost + 1
    • ヒープhpに（next_cost、nex_pos、nex_bus）を挿入します
• 戻り値-1

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

例

from collections import defaultdict
from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, connections):
      start = 0
      target = max(max(y, x) for y, x, _ in connections)

      adj = defaultdict(list)
      for f, t, id in connections:
         adj[f].append((t, id))

      hp = [(0, start, -1)]
      seen = defaultdict(set)

      while hp:
         cost, cur_pos, cur_bus = heappop(hp)
         if cur_pos == target:
            return cost
         if cur_bus in seen[cur_pos]:
            continue
         seen[cur_pos].add(cur_bus)

         for nex_pos, nex_bus in adj[cur_pos]:
            next_cost = cost
            if nex_bus != cur_bus:
               next_cost += 1
            heappush(hp, (next_cost, nex_pos, nex_bus))

      return -1

ob = Solution()
matrix = [
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0],
   [3, 5, 1],
   [5, 0, 2]
]
print(ob.solve(matrix))

入力

matrix = [[0, 1, 0],  
[1, 2, 0],  
[2, 3, 0],  
[3, 5, 1],  
[5, 0, 2]]

出力

2