Марковские поезда
Дела у Нидерландской железнодорожной компании NS идут не очень хорошо. Из-за технических проблем они вынуждены отменять многие поезда без предварительного уведомления. Это, конечно, крайне раздражает студентов, которые ездят из дома в школу на поезде.
Худшее в этой ситуации — это случайность отмен. Никто не знает заранее, будет ли поезд отменен; об отмене сообщается только в момент официального времени отправления. Поскольку обычно существует более одного возможного маршрута из дома в школу, у людей часто остается чувство «если бы я знал это заранее, я бы выбрал другой маршрут».
Недавно статистический отдел NS нашел революционное решение этой проблемы. Они заметили, что некоторые поезда отменяются чаще, чем другие. Чтобы помочь пассажирам, они решили опубликовать эту информацию. Новые расписания будут указывать не только время отправления и прибытия каждого поезда, но и вероятность его отмены.
Программное обеспечение для планирования поездок от NS, которое обычно находит самый быстрый маршрут между станциями, должно быть обновлено, чтобы находить маршрут, который дает наилучшие шансы прибыть вовремя. Это помогает пассажирам избегать поездов, которые могут вызвать проблемы, и вместо этого выбирать немного более долгий, но более надежный маршрут до школы.
Имея новые расписания, станцию отправления и время, станцию назначения и желаемое время прибытия, найдите маршрут, который дает наилучшие шансы прибыть в пункт назначения вовремя.
Маршрут в данном случае — это просто упорядоченный список станций, посещаемых пассажиром, начиная со станции отправления и заканчивая станцией назначения. Пассажир будет придерживаться маршрута, каждый раз садясь на первый возможный поезд до следующей станции. Если поезд отменен, он просто будет ждать следующего поезда до этой станции.
Шанс прибыть вовремя принимается как вероятность того, что пассажир, следуя описанному выше маршруту, прибудет на станцию назначения до или в желаемое время прибытия. При расчете этой вероятности мы предполагаем, что поезда отменяются независимо друг от друга и в соответствии с вероятностями, указанными в расписании.
Входные данные
Первая строка ввода содержит одно положительное целое число, указывающее количество запусков. Для каждого запуска ввод следующий:
Строка с одним положительным целым числом n, количеством поездов в расписании (n ≤ 100).
n строк, описывающих расписание. Каждая строка описывает один поезд, указывая его станцию отправления x, время отправления t_x, станцию назначения y (x ≠ y), время прибытия t_y (t_x < t_y) и вероятность отмены p. Станции обозначаются заглавными буквами в диапазоне 'A' ... 'L'. Время указано в формате чч:мм с 00 ≤ чч < 24 и 00 ≤ мм < 60. Вероятность p — это десятичное действительное число с 0.0 ≤ p < 1.0. Элементы ввода разделены пробелами.
Строка со станцией отправления a, самым ранним временем отправления t_a, станцией назначения b (a ≠ b) и желаемым временем прибытия t_b (t_a < t_b). Идентификаторы станций и время такие же, как в расписании.
Выходные данные
Вывод состоит из двух строк для каждого запуска. Первая строка каждого запуска содержит наилучший возможный маршрут для пассажира в виде списка идентификаторов станций, разделенных пробелами. Вторая строка содержит вероятность того, что пассажир, следуя данному маршруту, прибудет вовремя. Вероятность должна быть отформатирована как десятичное действительное число с ровно одной цифрой перед десятичной точкой и ровно 4 цифрами после. Применяются обычные правила округления: округлять вверх, если следующая цифра будет ≥ 5, в противном случае округлять вниз.
Примечания
При пересадке на промежуточной станции самое раннее возможное время отправления — одна минута после времени прибытия.
Все времена в пределах одного дня; поездка не пересекает полночь.
Никогда не бывает, чтобы два или более поезда отправлялись с одной станции в одно и то же время до одной и той же станции назначения.
Ввод таков, что существует уникальный маршрут с максимальной вероятностью.
Пассажир будет придерживаться своего маршрута, всегда садясь на первый доступный поезд до следующей станции. Если поезд отменен, он будет ждать следующего поезда до этой станции. Он никогда не будет пытаться быть умнее, выбирая более быстрые поезда или другие маршруты.