DAYAQ MƏKTƏBLƏRİ
Desentralizasiya prosesi çərçivəsində dayaq məktəblərinin yaradılması məsələsi gündəmə gəldi. Rayonda bəzi yollarla birləşdirilmiş N kənd mövcuddur. Hangi kəndlərin birləşdirildiyi və bu yolların məsafələri məlumdur. Məqsəd, bütün kəndlərin şagirdlərinin dayaq məktəbinə çıxışını təmin etməkdir. Şagirdlər, məktəbə bir neçə marşrut varsa, ən qısa olanı seçəcəklər. Məktəbin elə bir kənddə yerləşdirilməsini tapın ki, oradan ən uzaq kəndə olan məsafə minimal olsun.
Giriş məlumatları:
Birinci sətirdə N - kəndlərin sayı (2 ≤ N ≤ 1000) və M - uzunluqları məlum olan yolların sayı (2 ≤ M ≤ N(N-1)/2)* verilmişdir.
Sonrakı M sətirdə yollar haqqında məlumat verilir - 3 ədəd (iki tam ədəd - yollarla birləşdirilmiş kəndlərin nömrələri və bir müsbət həqiqi ədəd - müvafiq yolun uzunluğu).
Çıxış məlumatları:
Birinci sətirdə dayaq məktəbinin yerləşdirilməsi lazım olan kəndin nömrəsini çıxarın. Əgər bir neçə uyğun kənd varsa, onların nömrələrini artan sırayla çıxarın.
İkinci sətirdə məktəbdən ən uzaq kəndə olan məsafəni 2 onluq dəqiqliklə çıxarın. Əgər məsələnin həlli yoxdursa, yalnız bir -1 ədədini çıxarın.
Dayaq məktəbi kənd №2-də yerləşdirilməlidir. Oradan digər kəndlərə olan məsafələr:
№1-ə - 5 km,
№3-ə - 2 km,
№4-ə - 5 km.Beləliklə, ən uzaq kənd 5 km məsafədə yerləşir.