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.