在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