程序查找在python中达到最终目标所需的最少总线数

假设我们有一个3矩阵，其中每行包含三个字段[src，dest，id]，这意味着总线具有从src到dest的路线。上一辆新巴士要花一单位的钱，但是如果我们坐同一辆车，我们只需要付一单位的钱。我们必须找到从位置0到终点站（最大的位置）乘公共汽车所需的最低费用。如果没有解决方案，则返回-1。

所以，如果输入像

则输出将为2，因为我们可以在位置0处取0，然后在位置3处下车。然后我们乘公共汽车1到达位置5。

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

• 开始：= 0

• 目标：=给定矩阵的最大位置

• adj：=一个空的映射

• 对于每个src，dest，连接中的id，执行

• 在adj [src]的末尾插入(dest,id)

• hp：=具有项(0,start,-1)的堆

• 看到：=一个空的映射

• 当hp不为空时，执行

• next_cost：=成本

• 如果nex_bus与cur_bus不同，则

• 将(next_cost,nex_pos,nex_bus)插入堆hp

• next_cost：= next_cost + 1

• 进行下一次迭代

• 返回成本

• (cost,cur_pos,cur_bus)：=堆hp的top元素，并从hp中删除top

• 如果cur_pos与目标相同，则

• 如果看到cur_bus [cur_pos]，则

• 将cur_bus插入到seen [cur_pos]

• 对于adj [cur_pos]中的每个(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