在Python中查找到达最终目标所需的最少公交车数量的程序

假设我们有一个n x 3的矩阵，其中每行包含三个字段[src，dest，id]，这表示公交车从src到dest有路线。搭乘新公交车需要支付一单位的费用，但如果我们在同一辆公交车上停留，则只需支付一单位的费用。我们必须查找从0位置乘坐公交车到最终站点（最大位置）所需的最小费用。如果没有解决方案，则返回-1。

因此，如果输入如下所示：

0	1	0
1	2	0
2	3	0
3	5	1
5	0	2

那么输出将是2，因为我们可以在位置0搭乘编号为0的公交车，到达位置3下车。然后我们搭乘编号为1的公交车到达位置5。

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

• start := 0
• target := 给定矩阵的最大位置
• adj := 一个空映射
• 对于每个连接中的src，dest，id，执行以下操作：
  • 在adj[src]的末尾插入(dest，id)
• hp := 一个包含元素(0，start，-1)的堆
• seen := 一个空映射
• 当hp不为空时，执行以下操作：
  • (cost，cur_pos，cur_bus) := 堆hp的顶部元素，并从hp中删除顶部
  • 如果cur_pos和target相同，则执行以下操作：
    • 返回费用
  • 如果在seen[cur_pos]中存在cur_bus，则继续进行下一次迭代
  • 将cur_bus插入seen[cur_pos]
  • 对于每个(adj[cur_pos]中的nex_pos，nex_bus)，执行以下操作：
    • next_cost := cost
    • 如果nex_bus与cur_bus不同，则执行以下操作：
    • next_cost := next_cost + 1
    • 将(next_cost，nex_pos，nex_bus)插入堆hp
• 返回-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