पायथन में एक रोड ट्रिप में इंटरकंट्री ट्रैवेल्स की न्यूनतम संख्या का पता लगाने का कार्यक्रम

मान लीजिए हमें एक सड़क यात्रा की योजना बनानी है जिसमें विभिन्न देशों के विभिन्न शहरों का दौरा करना शामिल है। हमारे पास सड़कों 'R' की एक सूची है, जहां प्रत्येक तत्व को (x, y, लागत) के रूप में वर्णित किया गया है। x सड़क के शुरुआती शहर को दर्शाता है, y सड़क के गंतव्य शहर को दर्शाता है, और लागत उस सड़क से यात्रा करने की लागत को दर्शाती है। हमारे पास एक सूची 'सी' भी है जहां प्रत्येक तत्व एक देश है और एक तत्व में उस देश के शहर शामिल हैं। अब, हमारे पास एक आरंभिक शहर 'एस' और एक गंतव्य शहर 'ई' भी है, और हम स्रोत शहर से गंतव्य शहर की यात्रा करना चाहते हैं। इस सारी जानकारी को देखते हुए, हमें यात्रा को पूरा करने के लिए न्यूनतम अंतरदेशीय यात्राओं का पता लगाना होगा और यात्रा के लिए यात्रा की कुल लागत का भी पता लगाना होगा। हमें इन दो मानों को आउटपुट के रूप में प्रिंट करना होगा।

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