Поймай проблему с самолетом из мирового финала ACM ICPC 2018

Question

Уже несколько дней я думаю об алгоритме этой проблемы .Я придумал разные решения, но ни одно из них не дало правильного результата.Я думал о направленном ациклическом графе, но кажется, что пассажир может совершить поездку туда и обратно, например, от станции 0 до 3, затем от 3 до 0, а затем от 0 до 1. Я был бы признателен, если кто-то может описатьалгоритм (а не код) этой проблемы.Чтобы упростить поиск, я поставил эту проблему и здесь.

Ваш самолет до финала ICPC вылетает в скором времени, и единственный способ добраться до аэропорта - на автобусе.,К сожалению, некоторые водители автобусов рассматривают возможность забастовки, поэтому вы не знаете, сможете ли вы добраться до аэропорта вовремя.Ваша цель состоит в том, чтобы спланировать свое путешествие таким образом, чтобы максимизировать вероятность попадания в ваш самолет.У вас есть подробная карта города, которая включает в себя все автобусные станции.Вы находитесь на станции 0, а аэропорт - на станции 1. У вас также есть полное расписание, когда каждый автобус покидает свою начальную станцию ​​и прибывает на конечную станцию.Кроме того, для каждого автобуса вы знаете вероятность того, что он действительно будет работать в соответствии с графиком, в отличие от того, что его водитель бастует и выводит автобус из эксплуатации.Предположим, что все эти события являются независимыми.То есть вероятность того, что данный автобус будет работать в соответствии с планом, не изменится, если вы знаете, работает ли какой-либо из других автобусов в соответствии с планом.Если вы прибываете до времени отправления автобуса, вы можете перейти на этот автобус.Но если вы прибудете точно во время отправления, у вас не будет достаточно времени, чтобы сесть на автобус.Вы не можете заранее проверить, будет ли данный автобус работать в соответствии с планом - вы узнаете, только когда попытаетесь сесть в автобус.Таким образом, если два или более автобусов покидают станцию ​​одновременно, вы можете попытаться сесть только на один из них.

Ввод

количество станций в городе,Следующая строка содержит одно целое число k (1 ≤ k ≤ 10 ^ 18), обозначающее время, в которое вы должны прибыть в аэропорт.Каждая из следующих m строк описывает один автобус.Каждая строка содержит целые числа a и b (0 ≤ a, b

Выход

Показать вероятность того, что вы поймаете свой самолет, при условии, что вы следуете оптимальному курсу действий.Ваш ответ должен быть верным с точностью до абсолютной ошибки 10 ^ −6.

Пример ввода

8 4
1000
0 1 0 900 0.2
0 2 100 500 1.0
2 1 500 700 1.0
2 1 501 701 0.1
0 3 200 400 0.5
3 1 500 800 0.1
3 0 550 650 0.9
0 1 700 900 0.1

Пример вывода

0.3124

Первая строка ввода содержит два целых числа m (1 ≤ m ≤ 10 ^ 6) и n (2 ≤ n ≤ 10 ^ 6), обозначающих количество шин и

Answer 1

Рассмотрите событие прибытия, связанное с каждой запланированной поездкой.

Если вы участвуете в прибытии, т. Е. Если вы действительно успешно совершаете запланированную поездку, то вы окажетесь на станции во время прибытия, и вырешить, что делать дальше.

Для каждого прибытия вы можете легко рассчитать наилучшую вероятность совершения вашего рейса, если вы уже знаете лучшие вероятности прибытия, которое вы могли бы получить на следующем.

Поскольку все прибытия, к которым вы, возможно, могли добраться, следующие * позже , если вы обрабатываете все возможные прибытия в обратном хронологическом порядке, вы можете рассчитать наилучшую вероятность совершения рейса после каждого прибытия, используя только те вероятности, которыеВы уже рассчитали.

Процесс заканчивается с наилучшей вероятностью вашего первоначального прибытия на станцию ​​0.

Если вы умны в реализации, все это занимает O (N log N) время.