Маршруты без шагов назад
Курьер не любит петлять. Он идёт от перекрёстка s к перекрёстку t по одному правилу: каждый следующий перекрёсток должен быть ближе к t по прямой, чем тот, на котором он стоит сейчас. Сколько у него разных маршрутов?
В городе n перекрёстков с целыми координатами в метрах и m участков улиц, по каждому можно идти в обе стороны. Маршрут — последовательность участков улиц, поэтому два разных участка между одними и теми же перекрёстками дают разные маршруты. Бывают и участки-петли, которые возвращаются на тот же перекрёсток. Если s = t, маршрут один — никуда не идти. Маршрутов бывает очень много, выведите их число по модулю 109 + 7.
Один из тестов — настоящие улицы Алматы из OpenStreetMap, от вокзала Алматы-2 до MEGA Alma-Ata.
Вход
В первой строке n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105). Дальше n строк с координатами перекрёстков x y (|x|, |y| ≤ 109), потом m строк a b — участок улицы между перекрёстками a и b (1 ≤ a, b ≤ n). В последней строке s и t.
Выход
Число маршрутов из s в t по модулю 109 + 7.
Примеры
Пример 1
9 12 0 0 100 0 200 0 0 100 100 100 200 100 0 200 100 200 200 200 1 2 2 3 4 5 5 6 7 8 8 9 1 4 2 5 3 6 4 7 5 8 6 9 9 1
6
Пример 2
5 4 0 0 300 0 300 200 -100 200 -100 50 2 3 3 4 4 5 5 1 2 1
0
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первое, что приходит в голову, — обойти все маршруты рекурсией. Сколько их от вокзала Алматы-2 до MEGA? Больше 1015. Где в этом переборе повторяется одна и та же работа?
2Подсказка 2
Число маршрутов из перекрёстка не зависит от того, как вы на него пришли. Если вы знаете ответы для всех соседей, которые ближе к t, ответ для самого перекрёстка — их сумма. В каком порядке считать, чтобы соседи всегда были готовы раньше?
3Идея
Обозначим W(u) — число маршрутов из u в t. Тогда W(t) = 1, а для остальных W(u) — сумма W(v) по всем участкам улиц u — v, у которых v ближе к t, чем u. Каждое слагаемое относится к перекрёстку с меньшим расстоянием до t, поэтому достаточно отсортировать перекрёстки по расстоянию до t и считать по возрастанию: к моменту счёта u все нужные W(v) уже в таблице. Это динамика по графу без циклов.
4Разбор
Расстояния сравниваем по квадрату: (x − xt)² + (y − yt)² — целое число, и сравнение точное. Корень и числа с плавающей точкой здесь опасны: в шестом тесте квадраты расстояний двух соседних перекрёстков — 1018 и 1018 − 27, а в 64-битном числе с плавающей точкой обе величины округляются к одному и тому же 1018. Сравнение «строго ближе» тогда врёт, и один из двух маршрутов пропадает.
Петли сами собой не участвуют: у петли конец не ближе начала. Два параллельных участка добавят сумму дважды, как и требуется. Считать можно, пока расстояние не превысило расстояние от s: дальние перекрёстки на ответ не влияют. В каждой клетке храним остаток по модулю 109 + 7.
Рекурсия с запоминанием тоже даёт верные числа, но в последнем тесте цепочка подзадач длиной 50 000: в Python она упрётся в предел глубины рекурсии, а в Go потребует большого стека. Цикл по отсортированному порядку от глубины не зависит.
4+Решение
5Сложность
Сортировка — O(n log n), сам счёт — O(n + m): каждый участок смотрится с двух концов. Память O(n + m).
6Типичные ошибки
- Перебор без запоминания. На Алматы маршрутов больше 1015 — не дождаться.
- Счёт в порядке номеров перекрёстков или по обходу в ширину от t. Сосед, который ближе по прямой, может оказаться и с большим номером, и в более далёком слое обхода.
- Расстояния в числах с плавающей точкой. Не проходит шестой тест.
- Произведения в 32-битных целых. Разность координат доходит до 2·109, её квадрат — до 4·1018: нужен int64.