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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个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。

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

  • 开始：= 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

    以上是 程序查找在python中达到最终目标所需的最少总线数 的全部内容， 来源链接： utcz.com/z/334687.html

    回到顶部