Всем доброго времени суток! Недавно изучил алгоритм Дейкстры и его реализацию с помощью контейнера set. Но для того чтобы он (алгоритм) работал верно нужно было держать в контейнере данные типу pair что уменьшало скорость работы, поэтому я решил написать к контейнеру компаратор:
struct cmp { bool operator()(int a, int b) const { return d[a] < d[b];} };
здесь массив d[] хранит кратчайшее расстояние к вершине i;
Когда я попробовал добавить в контейнер число b, такое что d[a]==d[b] и a!=b, то ничего не произошло (то есть нужное число не добавилось в контейнер а релаксация вершины прошла) и как последствие неверная работа алгоритма :(
Возможно ли как-то это исправить (обойти проблему), или придется пользоваться контейнером с pair? Можно ли это реализовать с помощью других встроенных структур данных?
P.S.: За ранние всем спасибо :)
UPD: Проблема решена, но вопрос реализации с помощью других структур остается открыт.
multiset
У multiset реализация такая же как в обычном set?
erase по значению удаляет все вхождения, а не только одно
Ясно, спасибо, но для Дейкстры такое не подходит :(
Можно делать erase по итератору, он удаляет единичный элемент. Но здесь есть свои тонкости с нахождением нужного элемента, так что, по видимому, вариант, предложенный dalex'ом наиболее подходящий.
Можно использовать priority_queue, вроде побыстрее (не знаю), но там нельзя удалять. На e-maxx написано, как это обойти.
Я всегда писал set с парами, и все работало хорошо. Но однажды наткнулся на задачу с Дейкстрой на informatics.msk.ru (что-то мне подсказывает, что Вы решаете именно ее), в которой set все-таки не вошел. Впрочем, Treap все поправил.
Нет, наткнулся на проблему решая эту задачу: Задача
По поводу этой задачи — у меня по ней Дейкстра отработал за 0.041. Конкретно с ней проблем с быстродействием быть не должно)
А можно Ваш id на acmp.ru ?
Хмм, обычная квадратная Дейкстра -- 0,012.
Можно ваш код посмотреть, что там не так, наверное.
Вот исходник: 6951989. Извините, но более гуманного способа показать код не придумал.
paste.ubuntu.com
Такое чувство, что данная строчка хорошенько так влияет на время работы. Да и вообще явно хранить граф в некоторых задачах, включая эту, бывает муторнее, чем неявно.
Кстати, Ваш код с парами замечательно прошел.
лол, задача на дп.
Дейксра — это ДП.
это понятно, я имел в виду другое дп.
Можно узнать, какое именно? В задаче ведь можно идти не только вправо или вниз. Так что нужен Дейкстра, Левит или БФ.
amazing_dp[i][j][step]
Это Беллман-Форд)
Спасибо огромное, это работает :)
а теперь я не понял, в чём была проблема? просто у pair такой же компаратор.
Нет, для pair можно использовать обычный компаратор (std::less) set <pair <int, int> > // вес — ребро
а теперь я не понял смысл этого коммента.
В set -е идет сортировка по первому int в паре (то есть по весу ребер к вершинам), а второй int — это сама вершина. Поробние: Your text to link here...
ты меня не понял или просто издеваешься. я понимаю, как реализовывается дийкстра через set< pair >, я не понял, почему ТЕБЕ не нравится этот способ. с топике ты написал, что из-за времени, но ведь у pair такой же по сути компаратор, как у dalex'a, а он тебе угодил.
Я просто не понял... На е-maxx'e написано что если избавится от pair то будет быстрее (а поскольку я только учи алгоритмы то питаюсь запоминать самые быстрые), но как показал сайт они идентичные по времени, но с pair "надежные".