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 := 一个空映射
  • 对于 connections 中的每个 src、dest 和 id，执行以下操作：
    • 将 (dest, id) 插入 adj[src] 的末尾
  • hp := 一个包含项目 (0, start, -1) 的堆
  • seen := 一个空映射
  • 当 hp 不为空时，执行以下操作：
    • (cost, cur_pos, cur_bus) := 堆 hp 的顶部元素，并从 hp 中删除顶部元素
    • 如果 cur_pos 与 target 相同，则
      • 返回 cost
    • 如果 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

更新于： 2020-12-03

254 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告