โปรแกรมหาจำนวนการเดินทางข้ามประเทศน้อยที่สุดในการเดินทางโดยรถยนต์ใน 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 -> 1 -> 3 ใช้ถนน [0, 1, 2] และ [1, 3, 3] การเดินทางข้ามประเทศ 2 ครั้ง ค่าใช้จ่ายรวม 2 + 3 = 5

ขั้นตอนการแก้ปัญหา

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