Поиск корабля

В условии задачи описан неориентированный невзвешенный граф. Обозначим через di длину кратчайшего пути от вершины s до вершины i. Значения di можно найти, запустив в графе поиск в ширину.

Обозначим через Ti множество всех вершин, лежащих на хотя бы одном кратчайшем пути из вершины s в вершину i. Найдем множества Ti для всех вершин графа. Для этого упорядочим вершины по возрастанию значения di, и в этом порядке будем строить искомые множества для вершин. Заметим, что если какой-то кратчайший путь из вершины s заканчивается в вершине v, то предпоследняя вершина этого пути может быть расположена в вершине u тогда и только тогда, когда dv = du + 1, а также вершины u и v соединены ребром. Таким образом, множество Tv — это объединение множеств Tu для всех подходящих вершин u. Также в множество Tv нужно не забыть добавить саму вершину v.

Для того, чтобы быстро построить множества Ti, воспользуемся битовым сжатием: его можно реализовать самостоятельно, либо с помощью структуры данных bitset. Эта структура данных позволяет хранить множества чисел от 1 до n и производить операцию объединения за время , где w — машинное слово, равное 32 или 64, в зависимости от параметров системы.

Для того, чтобы ответить на запрос, необходимо выяснить, какие вершины лежат на кратчайшем пути от s до v, причем расстояние до самих этих вершин от s равно k. Для того, чтобы получить множество всех таких вершин, возьмем множество вершин, которые лежат на кратчайших путях из s в v, и удалим из него все вершины, кроме тех, для которых di = k. Заметим, что так как мы упорядочили вершины в порядке возрастания величины di, искомые вершины будут образовывать непрерывный подотрезок, а значит, необходимые операции удаления с использованием битового сжатия можно сделать за время , используя операции битового сдвига. После того, как в множестве остались лишь подходящие вершины, необходимо вывести ответ: если множество пусто, то ответ 0, если в нем более одного элемента, то ответ  - 1, а в противном случае ответ — это вершина, которая содержится в найденном нами множестве. Для проверки всех этих условий за время также можно использовать битовое сжатие.

Асимптотика времени работы программы, а также памяти, используемой программой, составляет .