पायथन में अंतिम लक्ष्य तक पहुँचने के लिए आवश्यक न्यूनतम संख्या में बसें खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक n x 3 मैट्रिक्स है जहां प्रत्येक पंक्ति में तीन फ़ील्ड हैं [src, dest, id] इसका मतलब है कि बस में src से dest तक का मार्ग है। नई बस में चढ़ने में एक यूनिट पैसा लगता है, लेकिन अगर हम एक ही बस में रहते हैं तो हमें एक यूनिट ही देना पड़ता है। हमें बस को स्थान 0 से अंतिम पड़ाव (सबसे बड़ा स्थान) तक ले जाने के लिए आवश्यक न्यूनतम लागत का पता लगाना होगा। अगर कोई समाधान नहीं है तो वापसी -1.

तो, अगर इनपुट पसंद है

तब आउटपुट 2 होगा, क्योंकि हम स्थान 0 पर 0 ले सकते हैं और स्थान 3 पर निकल सकते हैं। फिर हम स्थान 5 पर पहुंचने के लिए बस 1 लेते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• शुरू:=0
• लक्ष्य :=दिए गए मैट्रिक्स का अधिकतम स्थान
• adj :=एक खाली नक्शा
• कनेक्शन में प्रत्येक स्रोत, गंतव्य, आईडी के लिए, करें
  • adj[src] के अंत में (dest, id) डालें
• hp:=आइटम के साथ एक ढेर (0, प्रारंभ, -1)
• देखा:=एक खाली नक्शा
• जबकि hp खाली नहीं है, करें
  • (लागत, cur_pos, cur_bus) :=हीप hp का शीर्ष तत्व और hp से शीर्ष हटाएं
  • यदि cur_pos लक्ष्य के समान है, तो
    • वापसी लागत
  • अगर cur_bus देखा में[cur_pos], तो
    • अगले पुनरावृत्ति के लिए जाएं
  • cur_bus को सीन में डालें[cur_pos]
  • adj[cur_pos] में प्रत्येक (nex_pos, nex_bus) के लिए, करें
    • अगली_लागत :=लागत
    • यदि nex_bus cur_bus के समान नहीं है, तो
      • अगली_लागत :=अगली_लागत + 1
    • हीप hp में (next_cost, nex_pos, nex_bus) डालें
• वापसी -1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

from collections import defaultdict
from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, connections):
      start = 0
      target = max(max(y, x) for y, x, _ in connections)

      adj = defaultdict(list)
      for f, t, id in connections:
         adj[f].append((t, id))

      hp = [(0, start, -1)]
      seen = defaultdict(set)

      while hp:
         cost, cur_pos, cur_bus = heappop(hp)
         if cur_pos == target:
            return cost
         if cur_bus in seen[cur_pos]:
            continue
         seen[cur_pos].add(cur_bus)

         for nex_pos, nex_bus in adj[cur_pos]:
            next_cost = cost
            if nex_bus != cur_bus:
               next_cost += 1
            heappush(hp, (next_cost, nex_pos, nex_bus))

      return -1

ob = Solution()
matrix = [
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0],
   [3, 5, 1],
   [5, 0, 2]
]
print(ob.solve(matrix))

इनपुट

matrix = [[0, 1, 0],  
[1, 2, 0],  
[2, 3, 0],  
[3, 5, 1],  
[5, 0, 2]]

आउटपुट

2