Одностороння вулиця
Einbahnstraße (німецькою для односторонньої вулиці) — це вулиця, на якій транспортні засоби можуть рухатися лише в одному напрямку. Однією з причин використання односторонніх вулиць є полегшення плавного потоку транспорту через переповнені райони. Це особливо корисно в центрах міст, зокрема в старих містах, таких як Каїр і Дамаск. Ретельне планування гарантує, що ви можете дістатися до будь-якого місця, починаючи з будь-якої точки. Проте водії повинні ретельно планувати свій маршрут, щоб уникнути подовження своєї поїздки через односторонні вулиці. Досвідчені водії знають, що існує кілька шляхів для подорожі між будь-якими двома місцями. Не тільки це, може бути кілька доріг між тими ж двома місцями. Знання найкоротшого шляху між будь-якими двома місцями є обов'язковим! Це ще важливіше при керуванні транспортними засобами, які важко маневрувати (сміттєвози, евакуатори тощо).
Ви щойно почали нову роботу в компанії з евакуації автомобілів. У компанії є кілька евакуаторів, припаркованих у гаражі компанії. Евакуатор піднімає передні або задні колеса зламаного автомобіля, щоб відбуксирувати його прямо назад до гаража компанії. Ви отримуєте дзвінки з різних частин міста про зламані автомобілі, які потрібно евакуювати. Автомобілі повинні бути евакуйовані в тому ж порядку, в якому ви отримуєте дзвінки. Ваше завдання — порадити водіям евакуаторів щодо найкоротшого шляху для збору всіх зламаних автомобілів назад у гараж компанії. Наприкінці дня ви повинні повідомити керівництву загальну відстань, яку подолали вантажівки.
Вхідні дані
Ваша програма буде перевірена на одному або декількох тестових випадках. Перша строка кожного тестового випадку вказує три числа (N, C і R), розділені одним або кількома пробілами. У місті є N місць з унікальними назвами, включаючи гараж компанії. C — це кількість зламаних автомобілів. R — це кількість доріг у місті. Зверніть увагу, що 0 < N < 100, 0 ≤ C < 1000, і R < 10000. Друга строка складається з C + 1 слів, перше з яких — це місце розташування гаража компанії, а решта — місця розташування зламаних автомобілів. Місце — це слово, що складається з 10 літер або менше. Розрізнення регістру літер є важливим. Після другої строки буде рівно R рядків, кожен з яких описує дорогу. Дорога описується за допомогою одного з цих трьох форматів:
A -v -> B
A <-v - B
A <-v -> B
A і B — це назви двох різних місць, тоді як v — це додатне ціле число (не перевищує 1000), що позначає довжину дороги. Перший формат вказує на односторонню вулицю від місця A до B, другий вказує на односторонню вулицю від місця B до A, тоді як останній вказує на двосторонню вулицю між ними. A, "стрілка" і B розділені одним або кількома пробілами. Кінець тестових випадків вказується рядком, що містить три нулі (для N, C і R).
Тестовий випадок у прикладі нижче такий самий, як і на малюнку.
Вихідні дані
Для кожного тестового випадку виведіть загальну відстань, використовуючи наступний формат:
k. V
Де k — це номер тестового випадку (починаючи з 1), пробіл, і V — це результат.