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

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程