โปรแกรมหาจำนวนขั้นต่ำของการเดินทางระหว่างประเทศในการเดินทางบนถนนใน Python

สมมุติว่าเราต้องวางแผนการเดินทางโดยต้องไปเยือนเมืองต่างๆ จากประเทศต่างๆ เรามีรายชื่อถนน 'R' ซึ่งแต่ละองค์ประกอบถูกอธิบายว่าเป็น (x, y, ราคา) x หมายถึงเมืองเริ่มต้นของถนน y หมายถึงเมืองปลายทางของถนน และราคาหมายถึงค่าใช้จ่ายในการเดินทางโดยถนนนั้น นอกจากนี้เรายังมีรายการ 'C' ซึ่งแต่ละองค์ประกอบเป็นประเทศ และองค์ประกอบหนึ่งประกอบด้วยเมืองของประเทศนั้น ๆ ตอนนี้ เรายังมี 'เมืองเริ่มต้น' และเมืองปลายทาง '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.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ต่อ :=แผนที่ใหม่โดยค่าเริ่มต้นคือ 0
• สำหรับ idx ดัชนีแต่ละรายการ และรายการองค์ประกอบใน C ให้ทำ
  • สำหรับแต่ละ k ในรายการ ทำ
    • ต่อ[k] :=idx
• adj_list :=แผนที่ใหม่ที่มีรายการเป็นค่า
• สำหรับแต่ละ a, b, wt ใน R, do
  • ถ้า cont[a] ไม่เหมือนกับ cont[b] แล้ว
    • wt :=wt + 10 ^ 10
  • ใส่คู่ (b, wt) ที่ส่วนท้ายของ adj_list[a]
• ระยะทาง :=แผนที่ใหม่ที่ค่าเริ่มต้นคือ 10 ^ 20
• ระยะทาง[s] :=0
• เข้าชมแล้ว :=ชุดใหม่
• t :=ฮีปใหม่ที่มีคู่ (0, s)
• ในขณะที่ t ไม่ว่าง ให้ทำ
  • คู่ (d, c) :=ป๊อปรายการที่เล็กที่สุดจากกอง
  • ถ้ามี c อยู่ในการเยี่ยมชมแล้ว
    • ติดตามตอนต่อไป
  • เพิ่ม c เพื่อเข้าชม
  • สำหรับแต่ละ j, wt ใน adj_list[c], do
    • ถ้าระยะทาง[j]> d + wt แล้ว
      • ระยะทาง[j] :=d + wt
      • ใส่คู่ (d + wt, j) ไปที่ heap t
• ผลตอบแทนคู่ (ค่าพื้นของ (ระยะทาง[e] / 10 ^ 10), (ระยะทาง[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)