पायथन में न्यूनतम लागत खोजने का प्रोग्राम ताकि नागरिकों को बाजार तक पहुंच प्राप्त हो सके

मान लीजिए, n संख्या में शहर हैं और m सड़कें शहरों को जोड़ती हैं। नागरिकों को बाजारों की आवश्यकता है जहां वे अपनी वस्तुएं खरीद सकें। अब, शहरों में कोई बाजार नहीं है, और शहरों के बीच की सड़कें निर्माणाधीन हैं। दो शहरों के बीच एक द्वि-दिशात्मक सड़क बनाई जा सकती है यदि (i) शहर में एक बाजार है; (ii) शहरों को उस सड़क द्वारा देखा जा सकता है जहां एक बाजार है। सड़क बनाने की लागत x है, और बाजार बनाने की लागत y है और वे दी गई हैं। हमें प्रत्येक शहर के नागरिकों को बाजारों तक पहुंच प्रदान करने की न्यूनतम लागत पता लगानी है। सरणी 'cities' में शहरों के बारे में जानकारी होती है कि कौन से शहर सड़क द्वारा जुड़े हो सकते हैं।

तो, यदि इनपुट n = 4, m = 3, x = 1, y = 2, cities = [[1, 2], [2, 3], [3, 4]] है, तो आउटपुट 4 होगा।

यहां, हम चार शहर 1, 2, 3 और 4 देख सकते हैं। यदि शहर 1 पर एक बाजार बनाया जाता है, और (1, 4) और (1,3) के बीच दो और सड़कें बनाई जाती हैं तो कुल लागत 2 + 1 + 1 = 4 होगी। यह न्यूनतम लागत है।

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

• यदि x <= y, तो
  • n * x लौटाएं
• अन्यथा,
  • adj_list := सूचियों को तत्वों के रूप में समाहित करने वाला एक मैप
  • cities में प्रत्येक city के लिए, करें
    • city1 := city[0]
    • city2 := city[1]
    • city2 को adj_list[city1] के अंत में डालें
    • city1 को adj_list[city2] के अंत में डालें
  • temp := मान True के साथ आरंभ की गई आकार (n + 1) की एक नई सूची
  • value := 0
  • dq := एक डबल-एंडेड क्यू
  • cur को 1 से n + 1 तक की रेंज में, करें
    • यदि temp[cur] शून्येतर है, तो
      • value := value + x
      • cur को dq के दाएं छोर पर डालें
      • temp[cur] := False
      • जब तक dq खाली नहीं है, करें
      • dq के बाएं छोर से निकाले गए तत्व के adj_list में प्रत्येक i के लिए, करें
        • यदि temp[i] शून्येतर है, तो
          • i को dq के दाएं छोर पर डालें
          • temp[i] := False
          • value := value + y
  • value लौटाएं

उदाहरण

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

from collections import defaultdict, deque def solve(n, m, x, y, cities): if x <= y: return n * x else: adj_list = defaultdict(list) for city in cities: city1 = city[0] city2 = city[1] adj_list[city1].append(city2) adj_list[city2].append(city1) temp = [True] * (n + 1) value = 0 dq = deque() for cur in range(1, n + 1): if temp[cur]: value += x dq.append(cur) temp[cur] = False while dq: for i in adj_list[dq.popleft()]: if temp[i]: dq.append(i) temp[i] = False value += y return value print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))

इनपुट

4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]] 

आउटपुट

4