Tək istiqamətli küçə
Einbahnstraβe (Alman dilində tək istiqamətli küçə) nəqliyyat vasitələrinin yalnız bir istiqamətdə hərəkət etməli olduğu bir küçədir. Tək istiqamətli küçələrin mövcudluğunun bir səbəbi sıx ərazilərdə nəqliyyatın daha rahat axmasını təmin etməkdir. Bu, xüsusilə Qahirə və Dəməşq kimi qədim şəhərlərin mərkəzlərində faydalıdır. Diqqətli planlaşdırma, hər hansı bir nöqtədən başlayaraq istənilən yerə çatmağı təmin edir. Bununla belə, sürücülər tək istiqamətli küçələr səbəbindən səyahətlərini uzatmamaq üçün marşrutlarını diqqətlə planlaşdırmalıdırlar. Təcrübəli sürücülər hər iki yer arasında bir neçə yol olduğunu bilirlər. Yalnız bu deyil, eyni iki yer arasında bir neçə yol ola bilər. Hər iki yer arasında ən qısa yolu bilmək vacibdir! Bu, manevr etmək çətin olan nəqliyyat vasitələrini (zibil maşınları, yedək maşınları və s.) idarə edərkən daha da vacibdir.
Siz yeni bir işə, avtomobil yedəkləmə şirkətində başlamısınız. Şirkətin qarajında bir neçə yedək maşını dayanıb. Yedək maşını, xarab olmuş avtomobilin ön və ya arxa təkərlərini qaldıraraq onu birbaşa şirkətin qarajına çəkir. Şəhərin müxtəlif yerlərindən yedəklənməsi lazım olan xarab avtomobillər haqqında zənglər alırsınız. Avtomobillər zəngləri aldığınız sıraya uyğun olaraq yedəklənməlidir. Sizin işiniz, yedək maşını sürücülərinə xarab avtomobillərin hamısını şirkətin qarajına toplamaq üçün ən qısa yolu məsləhət verməkdir. Günün sonunda, maşınların qət etdiyi ümumi məsafəni rəhbərliyə bildirməlisiniz.
Giriş verilənləri
Proqramınız bir və ya bir neçə test nümunəsi üzərində sınaqdan keçiriləcək. Hər bir test nümunəsinin ilk sətri bir və ya daha çox boşluqla ayrılmış üç rəqəmi (N, C və R) göstərir. Şəhərdə şirkətin qarajı da daxil olmaqla fərqli adlara malik N yer var. C xarab avtomobillərin sayıdır. R isə şəhərdəki yolların sayıdır. Qeyd edək ki, 0 < N < 100, 0 ≤ C < 1000 və R < 10000. İkinci sətir C + 1 sözlərdən ibarətdir, birincisi şirkətin qarajının yeri, qalanları isə xarab avtomobillərin yerləridir. Bir yer 10 hərf və ya daha azdan ibarət bir sözdür. Hərf ölçüsü əhəmiyyətlidir. İkinci sətirdən sonra, hər biri bir yolu təsvir edən dəqiq R sətir olacaq. Bir yol bu üç formatdan biri ilə təsvir olunur:
A -v -> B
A <-v - B
A <-v -> B
A və B iki fərqli yerin adlarıdır, v isə yolun uzunluğunu göstərən müsbət tam ədəddir (1000-dən çox olmayaraq). Birinci format A yerindən B yerinə tək istiqamətli küçəni göstərir, ikinci format B yerindən A yerinə tək istiqamətli küçəni göstərir, sonuncusu isə onların arasında iki istiqamətli küçəni göstərir. A, "ox" və B bir və ya daha çox boşluqla ayrılır. Test nümunələrinin sonu üç sıfırdan ibarət bir sətirlə göstərilir (N, C və R üçün).
Aşağıdakı nümunədəki test nümunəsi şəkildəki ilə eynidir.
Çıxış verilənləri
Hər bir test nümunəsi üçün aşağıdakı formatdan istifadə edərək qət edilən ümumi məsafəni çap edin:
k. V
Burada k test nümunəsinin nömrəsidir (1-dən başlayaraq), bir boşluq və V nəticədir.