کشوری با $n$ شهر داده شده است. در حال حاضر جاده‌ای بین شهرها نیست ولی می‌توانیم بین هر دو شهری که بخواهیم یک جاده‌ی دوطرفه بسازیم. هزینه‌ی ساخت هر جاده $\alpha$ واحد است. پس٬ هزینه‌ی کل ساخت $\alpha$ برابر تعداد جاده‌هایی می‌شود که می‌سازیم. در این کشور وقتی از یک جاده عبور کنیم باید یک واحد پول به عنوان عوارض پرداخت کنیم. حال فرض کنید که پس از ساخت جاده‌های موردنظرمان بخواهیم از شهر دل‌خواه $i$ به شهر دل‌خواه $j$ برویم. ممکن است برای رسیدن از $i$ به $j$ مسیرهای مختلفی موجود باشد (یک مسیر می‌تواند شامل عبور از چند جاده باشد). هزینه‌ی هر مسیر تعداد جاده‌های آن است. $d_{i,j}$ را هزینه‌ی کوتاه‌ترین (کم‌جاده‌ترین) راه بین $i$ و $j$ بنامید. اگر بین $i$ و $j$ هیچ راهی وجود نداشته باشد٬ مقدار $d_{i,j}$ برابر بی‌نهایت خواهد بود. مقدار عوارض پرداختی بین دو شهر $i$ و $j$ برابر $d_{i,j}$ خواهد بود. «هزینه‌ی کل جاده‌ها» برای یک کشور را برابر مجموع هزینه‌ی ساخت جاده‌ها و جمع عوارض‌ها به ازای هر دو شهر $i$ و $j$ تعریف می‌کنیم. مثلاً اگر $n$ برابر ٬۳ و مقدار $\alpha$ برابر ۱۰ باشد٬ و ما یک جاده بین شهرهای ۱ و ٬۲ و یک جاده هم بین شهرهای ۲ و ۳ بسازیم٬ آن‌گاه هزینه‌ی ساخت برابر ۲۰= $\alpha$۲ و مقدار عوارض برابر ۴ = ۱ + ۲ + ۱ = $d_{۲,۳}$ + $d_{۱,۳}$ + $d_{۱,۲}$ و بنابراین هزینه‌ی کل جاده‌های آن برابر ۲۴ خواهد بود. می‌خواهیم طوری جاده‌های کشور را بسازیم که هزینه‌ی کل جاده‌های آن کمینه شود. این مقدار کمینه را بر حسب $n$ و $\alpha$ به دست آورید. (راهنمایی: $\alpha \le ۱$ و $۱ \lt \alpha$ را جداگانه بررسی کنید.)

• سوال بعد
• سوال قبل