[ UVa ] 11228 - Transportation system

• আমাদের কে গ্রফল্যান্ডের শহরগুলির যে co-ordinate দেয়া থাকবে  তাদের সবগুলি থেকে সবগুলির দূরত্ব বের করে সেটা কে ওয়েট ধরে একটা গ্রাফ বানাতে হবে । 
• এই গ্রাফ থেকে MST বের করেত  হবে । 
• আমাদের মূল গ্রাফ থেকে MST বের করার সময় যখন প্রতিবার একটা করে নতুন এজ নিব তখন চেক করতে হবে নতুন এজটার ওয়েট আমাদের Threshold ( r )  থেকে বড় কি না ? 
• যদি সেটা r থেকে বড় হয় তবে সেই এজটা ওয়েট rail roads extension এ যোগ করতে হবে । আর যদি সেটা r থেকে ছোট হয় তবে সেটা state roads extension এ যোগ করতে হবে । 
• মোট states সংখ্যা = mst তে  মোট node সংখ্যা - মোট এজ সংখ্যা [ rail road এজ বাদে ] 
• প্রিন্ট Extension rounded to the nearest integer ;) 

কোড : 

হ্যাপি কোডিং :D