آقا میکائیل از شما می‌خواهد تا برای نهار فردا ‎$k$‎ کیلو برنج بخرید. شما از آقای شیری ماشین باشگاه را می‌گیرید و تصمیم می‌گیرید از مغازه‌های اطراف برنج را تهیه کنید. خوشبختانه نقشه‌ی مغازه‌های اطراف باشگاه به شکل یک گراف وزن دار ‎$n$‎ راسی در داشبورد ماشین قرار دارد که در آن هر راس معادل یک مغازه و هر یال معادل هزینه‌ای است که شما برای رفتن از یک مغازه به مغازه‌ی دیگر با ماشین باشگاه باید بپردازید (ازجمله پول بنزین). توجه کنید که در این نقشه خود باشگاه هم به شکل یک راس مشخص شده است. همچنین در پشت نقشه راهنمایی قرار دارد که قیمت فروش برنج در هر مغازه را نوشته است. از آنجا که بیشتر خریدن برنج باعث می‌شود که تخفیف بیشتری بگیرید، به ازای هر مغازه ‎$k$‎ عدد در راهنما نوشته شده است، که عدد ‎$i$‎ام آن نشان دهنده‌ی هزینه خرید ‎ $i$‎کیلو برنج از آن مغازه می‌باشد و این ‎$k$‎ عدد لزوما رابطه‌ی خطی ندارند. در حین خروج از باشگاه آقای شیری از شما می‌خواهد که با کمترین هزینه برنج را تهیه کنید و به باشگاه برگردید، در غیر این صورت از دوره‌ی تابستانی حذف می‌شوید. شما خوابتان را برای یکی از طراحان سوال دوره تابستانی تعریف می‌کنید. حال الگوریتمی از ‎$O(nk(n+k))$‎ ارائه دهید تا با گرفتن نقشه‌ی راهنما، کمترین هزینه برای خرید ‎$k$‎ کیلو برنج و بردن آن‌ها به باشگاه را پیدا کند.

• سوال قبل