Marşrutlaşdırma (Bürünc)

Fermasındakı soyuq qış havasından bezmiş inək Bessi istirahət üçün daha isti bir yerə uçmaq fikrindədir. Təəssüf ki, o, yalnız bir aviaşirkətin — Air Bovinia-nın inəklərə bilet satmağa razı olduğunu, üstəlik bu biletlərin bir qədər mürəkkəb olduğunu aşkar edir.

Air Bovinia-ya məxsus $n$ təyyarə var və hər biri ən azı iki şəhərdən ibarət müəyyən bir "marşrut" üzrə işləyir. Məsələn, bir təyyarə $1$-ci şəhərdən başlayan, sonra $5$-ci şəhərə, sonra $2$-ci şəhərə və nəhayət $8$-ci şəhərə uçan marşrut üzrə hərəkət edə bilər. Bir şəhər marşrutda birdən çox dəfə görünə bilməz.

Bessi hər hansı bir marşrutdan istifadə etməyi seçərsə, marşrut boyunca istənilən şəhərdə təyyarəyə minə bilər və marşrutda daha sonra görünən istənilən şəhərdə düşə bilər. O, mütləq ilk şəhərdə minmək və ya son şəhərdə düşmək məcburiyyətində deyil. Hər marşrutun sabit bir dəyəri var və Bessi bu marşrutun hər hansı bir hissəsindən istifadə edirsə, marşrut boyunca neçə şəhər ziyarət etməsindən asılı olmayaraq, bu dəyəri ödəməlidir.

Bessi öz fermasından (şəhər $A$-dan) tropik təyinat nöqtəsinə (şəhər $B$-yə) səyahət etməyin ən ucuz yolunu tapmaq istəyir. Mürəkkəb bir marşrutla məşğul olmaq istəmədiyi üçün yalnız bir marşrutdan istifadə etmək istəyir. Zəhmət olmasa ona ödəməli olduğu minimum məbləği müəyyən etməkdə kömək edin.