Piyada və velosipedçi

İki komanda yoldaşı söhbətə dalıb vaxtın necə keçdiyindən xəbərsiz oldular. Birdən-birə onlar Dünya Proqramlaşdırma Çempionatının dörddəbir finalına gecikdiklərini və şəhərin o biri başında olduqlarını anladılar. Xoşbəxtlikdən, onlardan birinin velosipedi var idi. Lakin, yarışma qaydalarına əsasən, komanda bütün üzvləri gələnə qədər yarışa başlaya bilməz, yəni ən sondan gələn yoldaşın nə vaxt çatması vacibdir. Əgər onlardan biri velosipedi götürüb finişə çatsa, digəri bütün yolu piyada getməli olacaq. Hər ikisi velosiped sürməkdə bərabər səviyyədədir, yəni eyni sürətlə hərəkət edirlər, amma təəssüf ki, velosipedi birlikdə sürə bilməzlər.

Yoldaşlar tez bir marşrut tərtib edib yarış meydançasına çatmaq üçün plan qurdular. Marşrut $N$ kəsişmədən və onları birləşdirən $M$ tək istiqamətli yoldan ibarətdir. Hər hansı bir kəsişmədən çıxandan sonra geri qayıtmaq mümkün deyil. Dostlar başa düşdülər ki, müəyyən bir məsafə qət edəndən sonra velosipedi xüsusi parklama yerində qoymaq olar ki, piyada gedən digər yoldaş onu götürüb yoluna velosipedlə davam etsin. Beləliklə, ümumi səyahət vaxtını azaltmaq mümkündür. Sizin vəzifəniz - ən az vaxtda finişə çatmağın mümkün olub-olmadığını və velosipedin yalnız kəsişmələrdə olan xüsusi park yerlərində buraxıla biləcəyini nəzərə alaraq (əks halda velosipedi itirmək riski var), bu minimum vaxtı müəyyənləşdirməkdir.