Тема: Задача со spoj.pl
посмотрите кому не лень https://www.spoj.pl/problems/SHPATH/
я решал алгоритмом Дейкстры, расстояния хранил в set.
Получаю TL.
Что можете посоветовать?
Re: Задача со spoj.pl
Вместо сета лучше использовать priority_queue.
Re: Задача со spoj.pl
Ещё можно попробовать вместо пар в очереди хранить только номера вершин (но с другим компаратором). Я это описал в недавно переписанной статье Алгоритм Дейкстры для разреженного графа.
P.S. Посмотрел задачу, там же даже не сказано, сколько рёбер. А если их там 10000 из каждой вершины будет? Тогда выгодней даже будет обычную Дейкстру написать, за N^2+M.
Re: Задача со spoj.pl
Ну сначала писалась обычная...
Re: Задача со spoj.pl
помогло только написание кучи
Re: Задача со spoj.pl
Интересно, а такую идею если попробовать.
Там же сказано, что длина любого пути <= 2*10^5? Что, если мы вместо кучи сделаем такую вещь: для каждого расстояния i сохраним список (вектор) vs[i ] вершин, имеющих такое расстояние. При релаксации будет добавлять вершину в список для нового расстояния (а из старого списка удалять не будем - это долго, O(1) здесь никак не получится). А в начале каждой итерации будем выбирать текущую вершину следующим образом: сделаем глобальный указатель cur_d = 0, а в начале каждой итерации будем извлекать (и удалять) из списка vs[cur_d] какую-то вершину v, смотреть - если она поюзана, то взять следующую вершину из списка (когда список опустеет, сделать ++cur_d), иначе эта v и есть нужная нам ближайшая из непоюзанных вершин.
Асимптотика получается: O(M) на все релаксации, и, т.к. суммарный размер списков есть O(MAXLEN+M), то на выбор текущей вершины тоже асимптотика O(MAXLEN+M). Итого: O(MAXLEN+M), хорошая асимптотика, близкая к оптимальной (оптимальная, когда M>=MAXLEN).