Cənab Çudakovun avtobusları

Cənab Çudakov bir dəfə müəyyən bir kapital topladı (heç kimin cəsarət etmədiyi bir layihəni uğurla həyata keçirərək) və sərnişin daşımaları biznesinə sərmayə qoymağa qərar verdi. O, artıq şəhərlər toplusunu seçib və onların arasında əlaqə yaratmaq istəyir. Bundan əlavə, o, marşrutlarındakı dayanacaqların ardıcıllığının həmişə ən kiçik addan ən böyük ada qədər leksikoqrafik qaydada sıralanmasına qəti qərar verib ("leksikoqrafik" o deməkdir ki, sözləri müqayisə edərkən əvvəlcə ilk hərflər, əgər onlar eynidirsə, ikinci hərflər və s. müqayisə olunur). Tanışları onu bunun həmişə rahat olmadığını inandırdılar (məsələn, Vinnitsa–Kiyev–Odessa–Sevastopol–Xarkov–Yalta). Buna görə də, indi cənab Çudakov kompromis variantı üzərində düşünür: iki avtobus marşrutu hazırlamaq, belə ki, onların ümumi başlanğıcı (leksikoqrafik olaraq ən kiçik şəhər) və sonu (leksikoqrafik olaraq ən böyük şəhər) olsun, hər marşrut daxilində şəhərlərin ardıcıllığı sıralanmış olsun və hər şəhərdən ən azı bir marşrut keçsin. Məsələn, yuxarıda göstərilən şəhərlər üçün bu, Vinnitsa–Kiyev–Xarkov–Yalta və Vinnitsa–Odessa–Sevastopol–Yalta marşrutları ola bilər.

Cənab Çudakovun qərar verməsinə kömək edəcək bir proqram yazın. Proqram, şəhərlər arasındakı məsafələr cədvəlini oxuyaraq, bütün şəhərləri ardıcıllıqla ziyarət edərək marşrutun uzunluğunu və kompromis variantının tələblərinə cavab verən marşrut cütlüyünün minimal mümkün ümumi uzunluğunu tapmalıdır (hər ikisi leksikoqrafik olaraq ilk şəhərdə başlayır, leksikoqrafik olaraq son şəhərdə bitir, hər marşrut daxilində bütün şəhərlər sıralanır, hər şəhərdən ən azı bir marşrut keçir).