Марковські поїзди
У Нідерландської залізничної компанії NS справи йдуть не дуже добре. Через технічні проблеми вони змушені скасовувати багато поїздів без попереднього повідомлення. Це, звісно, дуже засмучує студентів, які їздять з дому до школи на поїзді.
Найгірше в цій ситуації - це випадковість скасувань. Ніхто не знає заздалегідь, чи буде скасовано поїзд; скасування оголошується лише в офіційний час відправлення. Оскільки зазвичай є більше одного можливого маршруту з дому до школи, люди часто залишаються з відчуттям "якби я знав це заздалегідь, я б вибрав інший маршрут".
Нещодавно статистичний відділ NS знайшов революційне рішення цієї проблеми. Вони помітили, що деякі поїзди скасовуються частіше, ніж інші. Щоб допомогти пасажирам, вони вирішили опублікувати цю інформацію. Нові розклади будуть вказувати не лише час відправлення та прибуття кожного поїзда, але й ймовірність його скасування.
Програмне забезпечення для планування подорожей від NS, яке зазвичай знаходить найшвидший маршрут між станціями, має бути оновлене, щоб знаходити маршрут, який дає найкращі шанси на вчасне прибуття. Це допомагає пасажирам уникати поїздів, які можуть створити проблеми, натомість обираючи трохи довший, але більш надійний маршрут до школи.
З огляду на нові розклади, станцію відправлення та час, станцію призначення та бажаний час прибуття, знайдіть маршрут, який дає найкращі шанси на вчасне прибуття до місця призначення.
Маршрут у цьому випадку - це просто впорядкований список станцій, які відвідує пасажир, починаючи зі станції відправлення і закінчуючи станцією призначення. Пасажир дотримуватиметься маршруту, кожного разу сідаючи на перший можливий поїзд до наступної станції. Якщо поїзд скасовано, він просто чекатиме на наступний поїзд до цієї станції.
Ймовірність вчасного прибуття вважається ймовірністю того, що пасажир, дотримуючись описаного маршруту, прибуде на станцію призначення до або в бажаний час прибуття. При обчисленні цієї ймовірності ми припускаємо, що поїзди скасовуються незалежно один від одного і відповідно до ймовірностей, зазначених у розкладі.
Вхідні дані
Перший рядок вхідних даних містить одне додатне ціле число, що вказує на кількість запусків. Для кожного запуску вхідні дані такі:
Рядок з одним додатним цілим числом n, кількістю поїздів у розкладі (n ≤ 100).
n рядків, що описують розклад. Кожен рядок описує один поїзд, вказуючи його станцію відправлення x, час відправлення t_x, станцію призначення y (x ≠ y), час прибуття t_y (t_x < t_y) та ймовірність скасування p. Станції ідентифікуються великими літерами в діапазоні 'A' ... 'L'. Час вказується у форматі hh:mm з 00 ≤ hh < 24 та 00 ≤ mm < 60. Ймовірність p - це десяткове дійсне число з 0.0 ≤ p < 1.0. Елементи введення розділені пробілами.
Рядок з станцією відправлення a, найранішим часом відправлення t_a, станцією призначення b (a ≠ b) та бажаним часом прибуття t_b (t_a < t_b). Ідентифікатори станцій та часи такі ж, як у розкладі.
Вихідні дані
Вихід складається з двох рядків для кожного запуску. Перший рядок кожного запуску містить найкращий можливий маршрут для пасажира у вигляді списку ідентифікаторів станцій, розділених пробілами. Другий рядок містить ймовірність того, що пасажир, дотримуючись даного маршруту, прибуде вчасно. Ймовірність повинна бути відформатована як десяткове дійсне число з точно однією цифрою перед десятковою крапкою і точно 4 цифрами після. Застосовуються звичайні правила округлення: округляти вгору, якщо наступна цифра буде ≥ 5, інакше округляти вниз.
Примітки
При пересадці на проміжній станції найраніший можливий час відправлення - на одну хвилину пізніше часу прибуття.
Усі часи в межах одного дня; подорож не перетинає північ.
Ніколи не трапляється, щоб два або більше поїздів відправлялися з однієї станції в один і той же час до однієї і тієї ж станції призначення.
Вхідні дані такі, що існує унікальний маршрут з максимальною ймовірністю.
Пасажир дотримуватиметься свого маршруту, завжди сідаючи на перший доступний поїзд до наступної станції. Якщо поїзд скасовано, він чекатиме на наступний поїзд до цієї станції. Він ніколи не намагатиметься бути розумнішим, обираючи швидші поїзди або інші маршрути.