মডিউল ১৫_৩ঃ Commandos

কমান্ডোদের একটি দলকে একটি গুরুত্বপূর্ণ দায়িত্ব দেওয়া হয়েছিল। তাদের একটি শত্রু সদর দপ্তর ধ্বংস করতে হবে. শত্রু সদর দপ্তর বেশ কয়েকটি ভবন নিয়ে গঠিত এবং ভবনগুলি রাস্তা দ্বারা সংযুক্ত। কমান্ডোদের অবশ্যই প্রতিটি বিল্ডিং পরিদর্শন করতে হবে এবং প্রতিটি বিল্ডিংয়ের গোড়ায় বোমা রাখতে হবে। তারা একটি নির্দিষ্ট বিল্ডিংয়ের ভিত্তি থেকে তাদের মিশন শুরু করে এবং সেখান থেকে তারা প্রতিটি বিল্ডিংয়ে পৌঁছানোর জন্য ছড়িয়ে পড়ে। কমান্ডোদের অবশ্যই ভবনগুলির মধ্যে যাতায়াতের জন্য দেয়া রাস্তাগুলি ব্যবহার করতে হবে। তাদের মধ্যে যে কেউ একের পর এক বিল্ডিং পরিদর্শন করতে পারে, কিন্তু তাদের কাজ শেষ হলে তারা অবশ্যই একই জায়গায় একত্রিত হবে। এই সমস্যায়, আপনাকে বিভিন্ন শত্রু সদর দফতরের বিবরণ দেওয়া হবে। আপনার কাজ হল মিশনটি সম্পূর্ণ করার জন্য প্রয়োজনীয় ন্যূনতম সময় নির্ধারণ করা। প্রতিটি কমান্ডো বিল্ডিংগুলির মধ্যে চলাচল করতে ঠিক এক ইউনিট সময় নেয়। আপনি অনুমান করতে পারেন যে একটি বোমা স্থাপনের জন্য প্রয়োজনীয় সময় নগণ্য অথাথ বোমা স্থাপনের জন্য কোন সময় লাগবে নাহ। প্রতিটি কমান্ডো unlimited সংখ্যক বোমা বহন করতে পারে এবং মিশনের জন্য কমান্ডো unlimited সৈন্য দেয়া হয়েছে।

ইনপুট

4 -> number of nodes 3 -> number of edge 0 1 2 1 1 3 0 3 -> Source and Destination

Graph টি এইরকম হবে

ধরুন, A,B commando রয়েছে। তারা 0 নোড থেকে মিশন শুরু করবে। এই মিশনের source = 0 এবং destination = 3, অথাথ সব commando মিশন শেষে 3 নোডে একত্রিত হবে।

এরপর A, B commando নোড 1 এ গেল এবং কাজ নোড 1 এর কাজ শেষ করলো। এখন পর্যন্ত মিশনটিতে সময় লেগেছে time = 1।

এখন A এবং B commando আলাদা হয়ে গেল। A commando গেল 2 নোডে এবং B commando গেল 3 নোডে। এখন পর্যন্ত মিশনটিতে সময় লেগেছে time = 2।

এরপর A commando নোড 1 এ যাবে, destination নোড 3 তে অন্য commando দের সাথে একত্রিত হওয়ার জন্য। এতে এখন পর্যন্ত মিশনটিতে সময় লেগেছে time = 3।

এখন A commando নোড 3 এ যাবে এবং অন্য commando দের সাথে একত্রিত হবে। এতে এখন পর্যন্ত মিশনটিতে সময় লেগেছে time = 4।

এই প্রব্লেমটি আউটপুট হবে 4 ।