मान लीजिए हमारे पास एक n x 3 मैट्रिक्स है जहां प्रत्येक पंक्ति में तीन फ़ील्ड [src, dest, id] होते हैं इसका मतलब है कि बस का रूट src से dest तक है। एक नई बस में चढ़ने के लिए एक यूनिट पैसे लगते हैं, लेकिन अगर हम उसी बस पर रहते हैं तो हमें केवल एक यूनिट देना पड़ता है। हमें स्थान 0 से अंतिम स्टॉप (सबसे बड़ा स्थान) तक बस लेने के लिए आवश्यक न्यूनतम लागत ढूंढनी है। यदि कोई समाधान नहीं है तो -1 लौटाएं।
इसलिए, यदि इनपुट इस तरह है
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 2 | 3 | 0 |
| 3 | 5 | 1 |
| 5 | 0 | 2 |
तो आउटपुट 2 होगा, क्योंकि हम स्थान 0 पर बस 0 ले सकते हैं और स्थान 3 पर उतर सकते हैं। फिर हम बस 1 लेकर स्थान 5 तक पहुंच सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- start := 0
- target := दिए गए मैट्रिक्स का अधिकतम स्थान
- adj := एक खाली मैप
- प्रत्येक src, dest, id के लिए connections में, करें
- (dest, id) को adj[src] के अंत में डालें
- hp := आइटम (0, start, -1) के साथ एक हीप
- seen := एक खाली मैप
- जब तक hp खाली नहीं है, करें
- (cost, cur_pos, cur_bus) := हीप hp का शीर्ष तत्व और hp से शीर्ष हटाएं
- यदि cur_pos, target के समान है, तो
- cost लौटाएं
- यदि cur_bus, seen[cur_pos] में है, तो
- अगले इटरेशन के लिए जाएं
- cur_bus को seen[cur_pos] में डालें
- cur_pos में प्रत्येक (nex_pos, nex_bus) के लिए adj में, करें
- next_cost := cost
- यदि nex_bus, cur_bus के समान नहीं है, तो
- next_cost := next_cost + 1
- (next_cost, nex_pos, nex_bus) को हीप hp में डालें
- -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