程序查找在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