पायथन में रोड ट्रिप में न्यूनतम अंतर-देश यात्रा खोजने का प्रोग्राम

मान लीजिए हमें एक रोड ट्रिप की योजना बनानी है जिसमें विभिन्न देशों के विभिन्न शहरों का दौरा करना शामिल है। हमारे पास सड़कों की एक सूची 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 और तत्व item के लिए C में, करें:
  • item में प्रत्येक k के लिए, करें:
    • cont[k] := idx
• adj_list := एक नया मैप जिसमें सूचियाँ मान के रूप में हों
• प्रत्येक a, b, wt के लिए R में, करें:
  • यदि cont[a] cont[b] के समान नहीं है, तो:
    • wt := wt + 10^10
  • जोड़े (b, wt) को adj_list[a] के अंत में डालें
• distance := एक नया मैप जहां डिफ़ॉल्ट मान 10^20 हैं
• distance[s] := 0
• visited := एक नया सेट
• t := एक नया हीप जिसमें जोड़ा (0, s) हो
• जब t खाली न हो, करें:
  • जोड़ा (d, c) := हीप से सबसे छोटा आइटम निकालें
  • यदि c visited में मौजूद है, तो:
    • अगले पुनरावृत्ति के लिए जाएं
  • c को visited में जोड़ें
  • adj_list[c] में प्रत्येक j, wt के लिए, करें:
    • यदि distance[j] > d + wt, तो:
      • distance[j] := d + wt
      • जोड़े (d + wt, j) को हीप t में डालें
• जोड़ा (floor(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)