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)。

因此，要从0到3旅行，我们采用路径0->1->3。此路径中采用的道路为[0, 1, 2]和[1, 3, 3]。因此，跨国的总旅行次数为2，总成本为2 + 3 = 5。

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

  • cont := 一个新的映射，其默认值为0
  • 对于每个索引idx和C中的元素item，执行：
    • 对于item中的每个k，执行：
      • cont[k] := idx
  • adj_list := 一个包含列表作为值的新映射
  • 对于R中的每个a, b, wt，执行：
    • 如果cont[a]与cont[b]不同，则：
      • wt := wt + 10 ^ 10
    • 在adj_list[a]的末尾插入一个(b, wt)对
  • distance := 一个新的映射，其默认值为10 ^ 20
  • distance[s] := 0
  • visited := 一个新的集合
  • t := 一个新的堆，包含一个(0, s)对
  • 当t不为空时，执行：
    • pair (d, c) := 从堆中弹出最小项
    • 如果c出现在visited中，则：
      • 进行下一次迭代
    • 将c添加到visited
    • 对于adj_list[c]中的每个j, wt，执行：
      • 如果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)

更新于：2021年10月16日

263 次浏览

启动您的 职业生涯

完成课程获得认证

开始
广告
© . All rights reserved.