Честная подсказка
Команда навигатора хочет ускорить поиск маршрутов: вместо Дейкстры запустить A*. Коллега уже посчитал подсказку — для каждого перекрёстка число h(v), оценку расстояния до финиша t. Прежде чем выпускать это в навигатор, подсказку нужно проверить. Если она хоть где-то обещает больше, чем на самом деле ехать, A* может отдать не самый короткий маршрут. А если она даже не завышает, но нарушает неравенство треугольника на какой-нибудь дороге, код A* без повторного открытия вершин тоже может ошибиться.
Подсказку называют согласованной, если h(t) = 0 и для каждой дороги между u и v длины w выполнено h(u) ≤ w + h(v) и h(v) ≤ w + h(u). Подсказку называют допустимой, если для каждого перекрёстка h(v) ≤ d(v, t), где d — длина кратчайшего пути по дорогам. Если от v до t не доехать, расстояние бесконечно, и подсказка там ничего не завышает.
Определите, какая перед вами подсказка.
Вход
В первой строке три числа n, m, t — число перекрёстков, число дорог и номер финиша (1 ≤ t ≤ n ≤ 30 000, 1 ≤ m ≤ 60 000). Дальше m строк a b w: двусторонняя дорога между перекрёстками a и b длиной w метров (1 ≤ w ≤ 106). Бывают петли и несколько дорог между одной парой. В последней строке n целых чисел h(1), …, h(n), 0 ≤ h(v) ≤ 1012.
Выход
Одну строку:
consistent, если подсказка согласованная;- иначе
admissible K, если она допустимая, где K — число дорог, на которых нарушено неравенство (хотя бы в одну сторону); - иначе
overestimates K, где K — число перекрёстков, в которых h(v) > d(v, t).
Тесты с 4-го по 8-й — настоящие улицы Алматы с финишем у Зелёного базара и пятью разными подсказками.
Примеры
Пример 1
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 9 6 4 5 0
consistent
Пример 2
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 11 3 5 6 0
admissible 2
Пример 3
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 9 6 4 8 0
overestimates 1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Одно из двух свойств проверяется, глядя на каждую дорогу по отдельности. Другое так не проверить: какое именно и почему?
2Подсказка 2
Чтобы узнать d(v, t) для всех v сразу, не нужно запускать поиск из каждого перекрёстка. Дороги двусторонние.
3Идея
Согласованность — свойство локальное: это условие на каждую дорогу и на финиш, его проверяют одним проходом по списку дорог. Допустимость — глобальное: она сравнивает подсказку с настоящими расстояниями до финиша. Их даёт один запуск Дейкстры из t: дороги двусторонние, поэтому расстояние от t до v равно расстоянию от v до t. Для ориентированного графа пришлось бы запускать Дейкстру из t по развёрнутым рёбрам.
4Разбор
Сначала проверяем согласованность: h(t) = 0 и оба неравенства на каждой дороге. Если всё выполнено, ответ consistent, и Дейкстра не нужна: согласованная подсказка всегда допустима. Это видно, если сложить неравенства вдоль кратчайшего пути v = v0, v1, …, vk = t: h(v0) ≤ w1 + h(v1) ≤ … ≤ w1 + … + wk + h(t) = d(v, t).
Обратное неверно, и второй пример это показывает. Там h(2) = 3, а до финиша от перекрёстка 2 на самом деле 8: подсказка сильно занижена, и поэтому соседи 1 и 4 рядом с ней выглядят «нарушителями»: 11 > 4 + 3 и 6 > 2 + 3. Завышения нет нигде, ответ admissible 2. Если согласованности нет, считаем Дейкстрой расстояния от t и сравниваем.
Четвёртый тест полезно разобрать отдельно. В нём подсказка — расстояние по прямой, округлённое вниз до метра, и кажется, что уж она-то честная: дорога не бывает короче прямой. Но в данных координаты перекрёстков и длины улиц уже округлены до метра, и на одном перекрёстке, в 890 м от базара по дорогам, прямая между округлёнными точками даёт 891. Ответ — overestimates 1, а неравенство треугольника нарушено на 113 дорогах. В статье об A* это обсуждается: на настоящих данных «очевидно честная» подсказка может врать на метр.
4+Решение
5Сложность
Проверка согласованности — O(m), Дейкстра — O((n + m) log n). Запускать поиск из каждого перекрёстка, чтобы узнать его расстояние до финиша, — O(n · (n + m) log n), и на 30 000 перекрёстков это часы.
6Типичные ошибки
- Проверять допустимость по дорогам. Условие «на каждой дороге всё в порядке» — это согласованность. Подсказка может нарушать его и при этом нигде не завышать: второй пример, седьмой и десятый тесты.
- Забыть про недостижимые перекрёстки. В одиннадцатом тесте второй остров не связан с финишем, подсказки там огромные, но расстояние бесконечно, и завышения нет.
- Забыть про h(t). Подсказка в самом финише обязана быть нулём: в двенадцатом тесте h(t) = 1, и это единственное завышение.
- 32-битные числа. Подсказки доходят до 1012, а сумма w + h не помещается в 32 бита.