HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序，找出公路旅行中最少需要跨越国家/地区的次数

pythonserver side programmingprogramming更新于 2026/1/11 15:40:17

假设我们要计划一次公路旅行，其中包括游览不同国家/地区的多个城市。我们有一个道路列表"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
  • 对于 C 中的每个索引 idx 和元素 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 存在于访问中，则
      • 进行下一次迭代
    • 将 c 添加到访问中
    • 对于 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)

相关文章

有用资源

打印 下一节:用 Python 编写程序来判断我们是否在游戏中获胜 ❯❮ 上一节:用 Python 编写程序来找出两种货币的兑换率