وحید به تازگی شغلی به عنوان پستچی پیدا کرده است. شهری که او در آن زندگی می‌کند شامل ‎$n$‎ تقاطع و ‎$m$‎ خیابان است. هر خیابان دو تقاطع را به یکدیگر متصل می‌کند و عبور از هر دوجهت در آن میسّر است. وحید هر روز بعد از کار از تقاطع ‎$s$‎ که پست‌خانه در آن قرار دارد تا تقاطع ‎$t$‎ که خانهٔ او در آن‌جاست می‌رود ‎($s \neq t$)‎. زمان رسیدن از یک سر هریک از خیابان‌های شهر به سر دیگر آن بر حسب دقیقه داده شده است (زمان رسیدن از سر هر خیابان تا سر دیگر آن عددی صحیح و مثبت است). اگر وحید ‎$k$‎ دقیقه بعد از اتمام کارش به خانه برسد باید ‎$k$‎ تومان به همسرش پرداخت کند‎!‎ در برخی از تقاطع‌های شهر خانه وجود دارد (در هر تقاطع حداکثر یک خانه) که نامه آن‌ها در پست‌خانه است و وحید می‌تواند بعد از کار، در راه خانه بعضی از این نامه‌ها را به مقصدشان برساند و به ازای هر نامه یک تومان انعام دریافت کند.

وحید می‌خواهد مسیری را از پست‌خانه تا خانهٔ خود انتخاب کند که با رساندن نامه‌های سر راه و دریافت انعام، بخشی از هزینه‌ای که باید به همسرش بپردازد را جبران کند و کم‌ترین پول ممکن را بپردازد. یعنی اگر ‎$k$‎ دقیقه بعد از کار به خانه برسد و در راه ‎$p$‎ نامه را برساند، می‌خواهیم ‎$k-p$‎ مینیمم مقدار ممکن را داشته باشد. الگوریتمی از ‎$O(n^2)$‎ ارائه دهید که با دریافت تعداد تقاطع‌ها، خیابان‌های بین این تقاطع‌ها (به شکل یک ماتریس ‎$n\times n$‎) و محل کار و محل زندگی وحید، این مقدار مینیمم را به‌دست آورد.

توجه کنید ممکن است وحید از مسیری به خانه برود که دیرتر از سریع‌ترین مسیر به خانه برسد ولی به نفع او باشد.

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