- এই সমস্যা তে আমাদের কে এমন একটা সিটি বের করতে হবে যে জায়গা তে আমরা প্রফেসারের সাথে দেখা করতে পারব । এবং আমাদের খরচ হবে মিনিমাম হবে যদি প্রফেসারে সাথে আমাদের দেখা করা সম্ভব হয় ।
- এই জন্য আমরা আমাদের অবস্থান থেকে সবচেয়ে কম খরচে কোথাই কোথাই যেতে পারি সেটা বের করতে হবে ।
- এরপর প্রফেসর তার অবস্থান থেকে সবচেয়ে কম খরচে কোথাই কোথাই যেতে পারে সেটা বের করতে হবে ।
- এখন যে সকল সিটি তে প্রফেসর ও আমরা উভয়ে যেতে পারি সেই সিটি গুলো একটা ভেক্টরে জমা রাখতে হবে ।
- ভেক্টরের যে সিটির খরচ সবচেয়ে কম হবে । সেটই আমাদের ও প্রফেসসের মিটিং করা জন্য সবচেয়ে ভাল জায়গা এবং সেটাই প্রিন্ট করতে হবে । যদি এই রকম একাধিক জায়গা থাকে তবে সবগুলি শহর কে lexicographical order এ প্রিন্ট করতে হবে ।
- যদি প্রফেসরের সাথে দেখা করা সম্ভব না হয় তবে প্রিন্ট আমরা You will never meet. প্রিন্ট করব ।
এই সমস্যা টি 2nd best MST বের করা সম্পর্কিত সমস্যা । এই সমস্যা সমাধান করার জন্য প্রথমে MST বের করতে হবে । MST বের করার পর আমরা চেক করবো সবগুলি নোড একই সেটে আছে কি না ? যদি না থাকে তবে No way প্রিন্ট করতে হবে । আর যদি সবগুলি একই সেটে থাকে তবে দেখব মোট নোড সংখ্যা ইনপুট দেয়া এজের থেকে ১ বেশি কি না? যদি কেবল মাত্র ১ বেশি হয় তবে 2nd best MST খুজে দেখার দরকার নাই । কারণ 2nd best MST পাওয়া যাবে না। এবং আমদের কে No second way প্রিন্ট করেতে হবে । যদি নোড থেকে এজের পার্থক্য ১ না হয় তবে আমাদের কে 2nd best MST খুজে বের করতে হবে । এবং আমাদের কে সেটাই প্রিন্ট করেতে হবে । এখন দেখা গেলও যে MST এবং 2nd best MST এর খরচ একই সেই ক্ষেত্রে আমদের কে প্রথমে পাওয়া MST খরচকেই প্রিন্ট করতে হবে । এই ক্ষেত্রে No second way প্রিন্ট করলে WA খেতে হবে । কোড :
Comments
Post a Comment