মনে করুন n সংখ্যক শহর আছে এবং শহরগুলো দু ধরনের রাস্তা দিয়ে সংযুক্ত: হাইওয়ে এবং শর্টকাট। এখন একটি মানচিত্র আছে যেখানে শুধু হাইওয়ে দেখানো হয়েছে এবং সব শর্টকাট অনুপস্থিত। পরিবহন বিভাগ শর্টকাট ও হাইওয়ে ব্যবহার করে শহরগুলো সংযুক্ত করার চেষ্টা করছে। দুটি শহরের মধ্যে শর্টকাট থাকে তখন, যখন তাদের মধ্যে হাইওয়ে থাকে না। আমাদের কাজ হলো একটি শুরুর শহর থেকে বাকি সব শহরে শর্টকাটের মাধ্যমে ন্যূনতম দূরত্ব বের করা।
যেমন, ইনপুট এমন হলে
এবং শুরু শহর (s) = 1 হলে, আউটপুট হবে 3 1 2।
শুধু শর্টকাট ব্যবহার করলে, শহর ১ এবং ২-এর মধ্যে পথ হবে 1→3→4→2, এবং খরচ হবে ৩।
একইভাবে,
১ এবং ৩: 1→3, খরচ ১।
১ এবং ৪: 1→3→4, খরচ ২।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
- graph := n সংখ্যক সেট ধারণকারী একটি লিস্ট
- edges-এ থাকা প্রতিটি (x, y) জোড়ার জন্য
- x := x - 1
- y := y - 1
- y কে graph[x]-এ ইনসার্ট করুন
- x কে graph[y]-এ ইনসার্ট করুন
- temp_arr := -1 মান দিয়ে n সাইজের একটি অ্যারে
- b_set := s - 1 কী ধারণকারী একটি ম্যাপ
- f := 0 থেকে n পর্যন্ত সংখ্যাগুলোর সেট এবং b_set-এর সেট ডিফারেন্স
- index := 0
- যখন b_set-এর সাইজ > 0, तब
- b_set-এ থাকা প্রতিটি a এলিমেন্টের জন্য
- temp_arr[a] := index
- nxt := graph-এর ভ্যালুগুলোর একটি ম্যাপ যা b_set-এর সাবসেট নয়
- f := f এবং nxt-এর সেট ডিফারেন্স
- b_set := nxt
- index := index + 1
- b_set-এ থাকা প্রতিটি a এলিমেন্টের জন্য
- temp_arr-এর নন-জিরো ভ্যালুগুলো রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
def solve(n, edges, s): graph = [set() for i in range(n)] for (x, y) in edges: x -= 1 y -= 1 graph[x].add(y) graph[y].add(x) temp_arr = [-1] * n b_set = {s - 1} f = set(range(n)).difference(b_set) index = 0 while len(b_set) > 0: for a in b_set: temp_arr[a] = index nxt = {f for f in f if not b_set.issubset(graph[f])} f = f.difference(nxt) b_set = nxt index += 1 return (' '.join(str(t) for t in temp_arr if t > 0)) print(solve(4, [(1, 2), (2, 3), (1, 4)], 1)) ইনপুট
4, [(1, 2), (2, 3), (1, 4)], 1
আউটপুট
3 1 2
