e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Dijkstra algorithm

Metro

Metronun sxemi l xətt üzərində yerləşən n stansiyadan ibarətdir. Hər stansiya bir və ya daha çox xəttə aiddir(bu halda həmin stansiyada düşüb oradan keçən istənilən xəttə keçmək olar). Hər bir xətt iki və ya daha çox stansiyadan ibarətdir, heç olmasa digər bir xətlə kəsişir. Metronun sxemi əlaqəlidir.

Bir xətdəki iki qonşu stansiyaya arasında istənilən istiqamətdə hərəkətə 2 dəqiqə, bir stansiya daxilində bir xətdən digər xəttə keçməyə 1 dəqiqə vaxt sərf olunur. İstənilən digər vaxt itkilərini nəzərə almamaq olar.

“Diez-produkt” firması menecerinin a stansiyasından b stansiyasının yaxınlığında yerləşən kompaniyanın ofisinə çatması üçün zəruri olan ən az vaxtı tapın.

Giriş verilənləri

Birinci sətirdə iki natural nl (1l10) ədədləri verilir. Sonrakı l sayda sətirdə metronun hər xəttindəki stansiyaların nömrələri ardıcıl yazılır. Sonuncu sətirdə başlanğıc və son stansiyaların nömrələri göstərilir. Bütün ədədlərin qiymətləri naturaldır və 70-i aşmır.

Çıxış verilənləri

Yeganə ədəd – göstərilən stansiyalar arasında hərəkətə sərf edilən ən az vaxt verilir.

prb68.gif

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
7 3
2 1 3
6 1 4 5
5 7
2 1 7 3
Çıxış verilənləri #1
10