Привет Codeforces!
У нас задача
Дан связный невзвешенный ориентированный граф с N вершинами и M ребер. И дается Q запросов. В каждом запросе дается две чисел, U и V. Верно ли утверждение что дистанция мин. пути от U до V, равен abs(d[v] - d[u]), где d[i] это мин. дистанция от 1-ой вершиной?
А если нет, как решать эту задачу?
P.S. Что если граф взвешенный?
Простите за Грамматику, Я плохо знаю русский язык.
Это верно если V родитель U или U родитель V . Но в общем случае неверно. Допустим для этого графа.
В общем случае это неверно и для невзвешенного графа. Вопрос "как решать" зависит от ограничений задачи.
Если ограничения на N, M и Q небольшие, то решается стандартно через запуск поиска кратчайших путей за O(N + M) (O(MlogN) / O(N2 + M) для взвешеннего случая) на каждый запрос.
Возможная оптимизация — обрабатывать запросы для одной стартовой вершины вместе, делая только один поиск кратчайших путей. При достаточно маленьком N это решение сводится к вычислению попарных минимальных расстояний за O(N3) алгоритмом Флойда.
Также существует эффективное решение для случая графа-дерева. В данном случае ищется ближайший общий предок (LCA) вершин U и V за O(1) / O(logN) с дополнительным предпросчетом за O(N) / O(NlogN), после чего длина пути ищется за O(1) как сумма разниц расстояний от корня.
А что если ограничение N, M, Q < 105
Если граф общего вида, то мне лично неизвестно способов ускорить вычисление длины кратчайшего пути в графе между двумя вершинами. Возможно, вы не указали какие-то особенности графа.
Если это задача из существующего контеста/архива задач, то было бы хорошо выложить ссылку на нее. Если же это задача получилась из какой-то реальной задачи, то у нее может и не быть эффективного по времени/памяти решения.
Я не знаю правильно ли это или нет, но попробуй что-нибудь такое:
Построй минимальный остов для этого ориентированно-взвешенного графа, потом у тебя получиться дерево, затем задача сводиться к нахождению длины наикратчайшего пути между вершинами (u, v), делаешь с помощью LCA O(logn) на запрос
Итоговая асимптотика O((n + q)logn + m)
UPD: Асимптотики O(logn) на запрос можно достигнуть с помощью Бинарного подъема
Мне кажется ваше утверждение неправильно. Например для этого графа
Можете ли вы высказаться почему? Жадность с минимальным остовом в графе чтобы превратить его в дерево, или что-то другое?
На приведенном выше примере минимальный остов включает ребра "1-2" и "1-3". В данном остове путь между вершинами 2 и 3 равен 9, а в изначальном графе — 7.