پس از گذار از تونل مردافکن، دانش‌پژوهان با مشقّت فراوان به روستای ‎«پلنگ‌افکن»‎ رسیدند.با پرس‌وجوی فراوان، آقای ‎«کاف»‎ دریافت که برای خلاص شدن از جنگل، آن‌ها باید همگی به روستای ‎«شیرافکن»‎ رفته و از آن‌جا با هواپیما به باشگاه دانش‌پژوهان جوان برگردند.

در همین حین، یکی از دانش‌پژوهان المپیاد کامپیوتر که با تلاش زیاد نقشه‌ی تمامی روستاهای آن سرزمین و جاده‌های بین‌شان را پیدا کرده بود، فهمید که کلاً آن سرزمین ‎$m$‎ روستا دارد که با ‎$e$‎ تا جادّه به هم وصل هستند و هر کدام از جادّه‌های بین روستاها یا ‎«روباه‌افکن»‎ هستند یا ‎«خرس‌افکن». عبور از هر یک از جادّه‌های ‎«روباه‌افکن»‎ به‌دلیل وجود روباه‌های چابک در آن، بایستی به سرعت انجام شود و دقیقاً یک روز طول می‌کشد. امّا عبور از جادّه‌های ‎«خرس‌افکن»‎ به‌دلیل وجود خرس‌های خوابیده در آن، بایستی به‌آرامی انجام شود و دقیقاً ‎$m-1$‎ روز طول می‌کشد. نیز، می‌دانیم حداقل یک مسیر از روستای ‎«پلنگ افکن‎«‎ به ‎«شیرافکن»‎ وجود دارد.

با فرض دانستن نقشه‌ی دقیق روستاها، جادّه‌ها و نوع آن‌ها، الگوریتمی از زمان اجرای ‎$O(e)$‎ ارائه دهید که دانش‌پژوهان بتوانند در کم‌ترین تعداد روز از روستای ‎«پلنگ‌افکن»‎ به روستای ‎«شیرافکن»‎ بروند. الگوریتم خود را تحلیل و اثبات کنید‎.

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

‎