在Python中查找公路游记中的最少跨国旅行次数

假设我们要计划一次跨国公路旅行，其中涉及访问来自不同国家的各种城市。 我们有一个道路列表“R”，其中每个元素都被描述为（x，y，cost）。 x表示道路的起始城市，y表示道路的目标城市，cost表示通过该道路旅行的成本。 我们还有一个列表’C’，其中每个元素都是一个国家，一个元素包含该国家的城市。 现在，我们还有一个起始城市“s”和目标城市“e”，我们希望从源城市出发前往目标城市。 给定所有这些信息，我们必须找出完成旅行所必需的最少跨国旅行次数以及旅行的总成本。 我们必须将这两个值输出。

因此，如果输入类似于R = [[0,1,2]，[1,2,2]，[0,2,3]，[1,3,3]]，C = [[0]，[1]，[2,3]]，s = 0，e = 3，则输出将为（2,5）。

因此，要解决这个问题，我们将遵循以下步骤 −

• cont：一个新的映射，其中默认值为0
• 对于C中的每个索引idx和元素item，执行以下操作
  • 对于项中的每个k，请执行以下操作
    • cont [k] = idx
• adj_list：包含列表作为值的新映射
• 对于R中的每个a，b，wt，执行以下操作
  • 如果cont [a]与cont [b]不同，则
    • wt：= wt + 10 ^ 10
  • 在adj_list [a]末尾插入一对（b，wt）
• 距离：一个新的映射，其中默认值为10 ^ 20
• distance [s] = 0
• visited：一个新的集合
• t：包含一对（0，s）的新堆
• while t不为空，执行以下操作
  • 从堆中弹出最小的项的对（d，c）：=对
  • 如果visited中存在c，则
    • 进入下一次迭代
  • 将c添加到visited中
  • 对于j，wt中的每个，在adj_list中执行以下操作
    • 如果distance [j]> d + wt，则
    • distance [j] = d + wt
    • 将对（d + wt，j）插入堆t
• 返回对（distance [e] // 10 ^ 10，（distance [e] mod 10 ^ 10））的返回值

例

让我们查看以下实现，以便更好地理解 –

from collections import defaultdict
from heapq import heappush, heappop

def solve(R, C, s, e):
cont = defaultdict(int)
for idx, item in enumerate(C):
    for k in item:
        cont[k] = idx

adj_list = defaultdict(list)
for a, b, wt in R:
    if cont[a] != cont[b]:
        wt += 10 ** 10
    adj_list[a].append((b, wt))

distance = defaultdict(lambda: 10 ** 20)
distance[s] = 0
visited = set()

t = [(0, s)]
while t:
    d, c = heappop(t)
    if c in visited:
        continue
    visited.add(c)
    for j, wt in adj_list[c]:
        if distance[j] > d + wt:
            distance[j] = d + wt
            heappush(t, (d + wt, j))

return distance[e] // 10 ** 10, distance[e] % 10 ** 10

print(solve([[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3))

输入

[[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]], [[0], [1], [2, 3]], 0, 3

输出

(2, 5)