11554. Успеть на
самолет
Ваш самолёт вскоре вылетает на
финал ICPC, и единственный способ добраться до аэропорта – воспользоваться
автобусом. К сожалению, некоторые водители подумывают о забастовке, поэтому Вы
не уверены, удастся ли прибыть вовремя. Ваша цель – спланировать поездку так,
чтобы максимизировать вероятность успеть на рейс.
Перед Вами находится подробная
карта города, на которой отмечены все автостанции. Вы находитесь на станции 0,
а аэропорт расположен на станции 1. У Вас есть полное расписание: для каждого
автобуса известно время отправления из начальной станции и время прибытия на
конечную. Кроме того, для каждого автобуса задана вероятность того, что он
действительно выйдет на линию, а его водитель не объявит забастовку.
Предполагается, что все эти события независимы. Иными словами, вероятность
того, что конкретный автобус будет работать по расписанию, не зависит от того,
работают ли другие автобусы.
Если Вы прибываете на станцию
раньше времени отправления автобуса, то можете попытаться сесть на него. Однако
если Вы прибываете ровно к моменту отправления, времени на посадку уже не
хватит. Заранее узнать, будет ли автобус курсировать по расписанию, невозможно –
это станет известно только в момент попытки посадки. Если со станции
одновременно отправляются несколько автобусов, Вы можете попытаться сесть
только на один из них.
Рассмотрим расписание,
изображённое на рисунке. В нём указаны станции отправления и назначения
нескольких маршрутов, а также времена отправления и прибытия. Рядом с
некоторыми маршрутами подписана вероятность того, что автобус действительно
выйдет на линию. Для маршрутов, у которых вероятность не указана, она считается
равной 100%.
Вы можете попытаться сесть на
самый ранний автобус. Если он поедет, то доставит Вас прямо в аэропорт, и
беспокоиться больше не о чем. Если же нет, ситуация усложняется. Можно
воспользоваться вторым автобусом до станции 2. Он отправится наверняка, но
тогда Вы опоздаете на третий автобус из списка, который позволил бы прибыть в
аэропорт вовремя. Четвёртый автобус, который Вы ещё можете успеть, имеет
вероятность выхода на линию всего 0.1. Это слишком рискованно, поэтому разумнее
остаться на станции 0 и дождаться пятого автобуса. Если удастся на него сесть,
далее можно попытаться пересесть на шестой автобус до аэропорта; если же и он
не выйдет на линию, у Вас всё ещё будет возможность вернуться на станцию 0 и
успеть на последний автобус, следующий напрямую в аэропорт.
Вход. В первой строке заданы два целых
числа m (1 ≤ m ≤ 106) и n (2
≤ n ≤ 106) – количество автобусных маршрутов и
число станций в городе. В следующей строке записано одно целое число k
(1 ≤ k ≤ 1018) – момент времени, к которому
необходимо прибыть в аэропорт.
Каждая из следующих m
строк описывает один маршрут. В строке заданы целые числа a и b (0 ≤ a, b
< n, a ≠ b) – начальная и конечная станции. Далее
следуют целые числа s и t (0 ≤ s < t ≤ k) –
время отправления со станции a и время прибытия на станцию b.
Последнее значение в строке – число p (0 ≤ p ≤
1, не более 10 знаков после запятой), обозначающее вероятность того, что
автобус будет работать по расписанию.
Выход. Выведите вероятность того, что Вы
успеете на самолёт, если будете действовать оптимально. Ответ должен быть
точным с абсолютной или относительной погрешностью не более 10-6.
|
Пример
входа 1 |
Пример
выхода 1 |
|
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 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
4 2 2 0 1 0 1 0.5 0 1 0 1 0.5 0 1 1 2 0.4 0 1 1 2 0.2 |
0.7 |
теория
вероятности
Для решения
задачи используем метод динамического программирования, в котором маршруты
рассматриваются по убыванию времени отправления.
Рассмотрим
следующее состояние:
·
пассажир находится на станции x в момент времени time.
Какова
максимальная вероятность добраться от x до аэропорта
вовремя при оптимальной стратегии? Обозначим эту величину best(x, time). Параметр time может
принимать значения вплоть до 1018, поэтому число состояний
бесконечно. Если мы стоим на станции и ждём, ситуация меняется только в моменты, когда
какой-то автобус отправляется. Поэтому будем рассматриваем только
моменты отправления автобусов.
Когда мы вычисляем best(B, S)
для некоторого маршрута, возможны переходы только к состояниям с большим
временем:
·
если автобус поедет, мы окажемся в точке (E, T),
·
если автобус не поедет, мы остаёмся в (B, S) и ждём следующий рейс.
В обоих случаях следующий момент
времени строго больше текущего. Значит, если обрабатывать маршруты в порядке
убывания времени отправления, все необходимые будущие значения
уже будут посчитаны.
Переходы динамики
Пусть рассматривается маршрут:
·
B → E, отправление S, прибытие T, вероятность выхода на линию p
Тогда имеется два варианта действий:
1. Мы пытаемся
ехать. Если
автобус едет, вероятность события равна p. Тогда мы попадаем в состояние (E, T) и далее действуем оптимально:
p * best(E, следующий рейс > T)
Если Вы прибываете ровно к
моменту отправления, времени на посадку уже не хватит. Поэтому ищем следующий
рейс на станции E, который строго больше T.
Если автобус отменён, вероятность
события равна 1 – p. Тогда мы остаёмся на станции B и ждём
следующий рейс:
(1 – p) * best(B, следующий рейс > S)
Если со станции одновременно
отправляются несколько автобусов, Вы можете попытаться сесть только на один из
них. Если автобус отменён, нельзя сесть на
другой автобус на станции B в момент S. Следует ждать
рейс, время отправления которого строго больше S.
2. Вообще не пытаемся ехать. Тогда переходим к следующему автобусу на той же станции:
best(B, следующий рейс ≥ S)
Таким образом,
переход имеет вид:
best(B, S) =
max(p * best(E, следующий рейс > T) + (1 – p) *
best(B, следующий рейс > S),
best(B, следующий рейс ≥ S))
Пример
Отсортируем
рейсы в первом примере по номеру станции и времени отправления. Справа приведем
пары (время отправления, номер рейса), отсортированные по времени отправления.
|
номер рейса |
станция отпр. |
станция приб. |
время отпр. |
время приб. |
вероят ность |
пара |
|
0 |
0 |
1 |
0 |
900 |
0.2 |
(0, 0) |
|
1 |
0 |
2 |
100 |
500 |
1.0 |
(100, 1) |
|
2 |
0 |
3 |
200 |
400 |
0.5 |
(200, 2) |
|
3 |
0 |
1 |
700 |
900 |
0.1 |
(500, 5) |
|
4 |
1 |
1 |
1001 |
1001 |
1.0 |
(500, 7) |
|
5 |
2 |
1 |
500 |
700 |
1.0 |
(501, 6) |
|
6 |
2 |
1 |
501 |
701 |
0.1 |
(550, 8) |
|
7 |
3 |
1 |
500 |
800 |
0.1 |
(700, 3) |
|
8 |
3 |
0 |
550 |
650 |
0.9 |
(1001, 4) |
Вычисляем
вероятности прибытия в аэропорт по убыванию времени отправления рейсов. Обозначение time+ означает время, строго
большее time.
best(1, 1001) = 1.0;
best(0, 700) = 0.1 *
best(1, 900+) = 0.1 * 1 = 0.1;
best(3, 550) = 0.9 *
best(0, 650+) + 0.1 * best(3, 550+) = 0.9 * 0.1 = 0.09;
best(2, 501) = 0.1 *
best(1, 701+) + 0.9 * best(2, 501+) = 0.1 * 1.0 + 0.9 * 0
= 0.1;
best(3, 500) = 0.1 *
best(1, 800+) + 0.9 * best(3, 500+) =
0.1 * 1.0 + 0.9 * 0.09 =
0.181;
best(3, 500) = max(best(3,
500), best(3, 550)) = max(0.181, 0.09) = 0.181;
best(2, 500) = 1.0 *
best(1, 700+) + 0.0 * best(2, 500+) = 1.0;
best(2, 500) = max(best(2,
500), best(2, 501)) = max(1.0, 0.1) = 1.0;
best(0, 200) = 0.5 *
best(3, 400+) + 0.5 * best(0, 200+) =
0.5 * 0.181 + 0.5 * 0.1 =
0.0905 + 0.05 = 0.1405;
best(0, 200) = max(best(0,
200), best(0, 700)) = max(0.1405, 0.1) = 0.1405;
best(0, 100) = 1.0 *
best(2, 500+) + 0.0 * best(0, 100+) = 1.0 * 0.1 = 0.1;
best(0, 100) = max(best(0,
100), best(0, 200)) = max(0.1405, 0.1) = 0.1405;
best(0, 0) = 0.2 * best(1,
900+) + 0.8 * best(0, 0+) =
0.2 * 1.0 + 0.8 * 0.1405 =
0.2 + 0.1124 = 0.3124;
best(0, 0) = max(best(0,
0), best(0, 100)) = max(0.3124, 0.1405) = 0.3124;
Реализация алгоритма
Определим структуру автобусного рейса Route. Она содержит:
·
B – начальная станция (откуда едет автобус);
·
E – конечная станция (куда едет автобус);
·
S – время отправления с начальной станции;
·
T – время прибытия на конечную станцию;
·
P – вероятность, что автобус выйдет на линию;
·
value – максимальная вероятность добраться до аэропорта (станция 1), если начать маршрут с этого
автобуса, и действовать дальше оптимально.
struct Route
{
int B, E;
long long S, T;
double P, value;
Автобусные маршруты сортируются:
·
по времени отправления S
bool operator<(const Route& r) const
{
return S < r.S;
}
};
Основная часть программы. Читаем входные данные.
scanf("%d %d %lld", &m, &n, &k);
Создаём список
всех маршрутов, сгруппированных по станции отправления. Вектор v имеет размер n – количество
станций. Таким образом,
·
v[i] содержит список всех автобусных маршрутов, отправляющихся
со станции i.
vector<vector<Route>> v(n);
for (int i = 0; i < m; i++)
{
scanf("%d %d %lld %lld %lf", &r.B, &r.E, &r.S, &r.T, &r.P);
Максимальная вероятность добраться до аэропорта из этого маршрута изначально не
известна, инициализируем ее 0.
r.value = 0.0;
Добавляем маршрут r в список маршрутов, начинающихся с r.B.
v[r.B].push_back(r);
}
Создадим фиктивный
рейс, который обозначает момент, когда пассажир уже в аэропорту (станция 1).
Начальная и конечная станции – аэропорт.
r.B = 1;
r.E = 1;
Вероятность успеха рейса 100%.
r.value = 1.0;
r.P = 1.0;
Время отправления и время прибытия – позже всех.
r.S = k + 1;
r.T = k + 1;
Добавляем
этот фиктивный рейс в список маршрутов, отправляющихся с аэропорта.
v[1].push_back(r);
Для каждой станции i
сортируем все маршруты, которые отправляются с этой станции (v[i]) по
времени отправления S. Это нужно, чтобы в дальнейшем эффективно искать
следующий рейс с помощью upper_bound.
for (int i = 0; i < n; i++)
sort(v[i].begin(), v[i].end());
Создадим единый порядок обработки
всех маршрутов по времени отправления, чтобы потом динамика шла от поздних
рейсов к ранним.
Объявим вектор пар ord,
который хранит для каждого маршрута:
1.
Время
отправления S.
2.
Индексы
маршрута: {i, j}
·
i – номер станции
·
j – номер маршрута в v[i]
То есть каждая запись в ord
говорит: “Маршрут
v[i][j] отправляется в момент времени S”.
vector<pair<long long, pair<int, int>>> ord;
for (int i = 0; i < v.size(); i++)
for (int j = 0; j < v[i].size(); j++)
ord.push_back({ v[i][j].S, {i, j} });
Сортируем вектор ord по возрастанию времени
отправления всех маршрутов, независимо от станции.
sort(ord.begin(),
ord.end());
В переменной вычисляем максимальную вероятность успеть на самолёт, начиная со станции 0 в момент
времени 0.
double ret = 0.0;
Перебираем маршруты в порядке убывания времени отправления, чтобы для текущего
рейса значения value для всех будущих рейсов (которые отправляются позже) уже были посчитаны и можно было
корректно вычислять оптимальную вероятность.
for (int itOrd = m; itOrd >= 0; itOrd--)
{
Время
отправления текущего маршрута занесем в переменную startTime.
long long startTime = ord[itOrd].first;
p – это пара индексов, которая позволяет найти текущий маршрут в массиве
маршрутов v: сам маршрут хранится в v[p.first][p.second].
auto p = ord[itOrd].second;
Если время отправления startTime
> k (нельзя успеть на самолёт), просто пропускаем маршрут.
if (startTime > k) continue;
st –
это номер
станции отправления текущего маршрута.
int st = p.first;
r –
это текущий
маршрут, для которого мы считаем value.
Route& r = v[p.first][p.second];
Инициализируем значение value для текущего
маршрута нулем.
r.value = 0.0;
query – это временный объект типа Route, который
нужен для поиска следующего рейса с помощью upper_bound. Мы не
используем все поля, только B и S, которые нужны для сравнения при поиске.
Route query;
Настраиваем query для следующего сценария: мы хотим найти первый
автобус с той же станции, который отправляется строго позже текущего времени S,
если этот автобус был отменен (не вышел на маршрут).
query.B = r.B;
query.S = r.S;
Ищем первый автобус из той же станции, который уходит позже.
auto it = upper_bound(v[st].begin() + p.second, v[st].end(), query);
if (it != v[st].end())
Если такой рейс существует, то увеличиваем r.value на вероятность успеха через него.
r.value += (1.0 - r.P) * it->value;
Рассмотрим сценарий, когда автобус
вышел на маршрут. В таком случае в момент времени T
мы окажемся на станции E. Подготавливаем объект query для поиска следующего рейса. Формируем запрос: “Найти автобус, который отправляется со станции E и позже
времени T”.
query.B = r.E;
query.S = r.T;
Переменная d содержит номер станции
E, куда мы приехали.
int d = r.E;
Следующий автобус после прибытия в
E ищем в списке
маршрутов v[d] при помощи бинарного поиска. Его время отправления из E
должно быть строго больше T, так как по
условию задачи известно, что если Вы прибываете ровно к
моменту отправления, сесть уже нельзя.
it = upper_bound(v[d].begin(), v[d].end(), query);
if (it != v[d].end())
Если такой рейс найден, значит на
него можно пересесть. Добавляем вклад вероятности p * best(E, следующий рейс > T).
r.value += r.P * it->value;
Пропускаем текущий автобус. То
есть мы даже не рассматриваем варианта садиться / не садиться в него. Ждем
следующий автобус на этой же станции.
Проверяем, существует ли следующий
автобус на этой станции. Напомним, что
текущий маршрут r хранится в v[p.first][p.second].
if (p.second + 1 < v[p.first].size())
Если автобус существует и
вероятность успешно добраться до аэропорта на нем больше, обновляем value. Здесь:
·
r.value –
вероятность успеха, если пытаться сесть на текущий автобус;
·
v[p.first][p.second
+ 1].value – вероятность успеха, если пропустить текущий автобус и ждать
следующий.
r.value = max(r.value, v[p.first][p.second + 1].value);
Обновляем общий ответ. Выбираем лучший вариант только
среди автобусов, которые отправляются из начальной (нулевой)
станции.
if (r.B == 0) ret =
max(ret, r.value);
}
Выводим ответ.
printf("%.6lf\n", ret);