Тема: Dijkstra with Set
Кто может реализовать дейкстру с set-ом на с++?
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Dijkstra with Set
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Кто может реализовать дейкстру с set-ом на с++?
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
Декстра с set-ом: http://e-maxx.ru/algo/dijkstra_sparse
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
Не совсем понял, Дейксра с Фенвиком? Такого алгоритма вроде нет. Если интересует просто дерево Фенвика, то вам сюда http://e-maxx.ru/algo/fenwick_tree
Не совсем понял, Дейксра с Фенвиком? Такого алгоритма вроде нет. Если интересует просто дерево Фенвика, то вам сюда http://e-maxx.ru/algo/fenwick_tree
Судя по всему, aza_inf имел ввиду применение Фенвика для поиска минимального элемента в массиве для алгоритма Дейкстры.
Сомневаюсь, что Фенвиком можно это сделать: он умеет искать минимумы, только когда значения невозрастают в процессе апдейтов. В Дейкстре же надо иногда извлекать минимумы, т.е. фактически присваивать их бесконечности. Если кто-то представляет, как для этого применить Фенвика - буду благодарен, если объяснят
странно, но уже второй раз я пишу дейкстру с сетом как на е-максе и она ТЛится, хотя у остальных проходит( причем там вроде как ошбка - q.erase(make_pair(d[to], to)). должно быть ведь q.erase(find(make_pair(d[to], to))), но так он выдаёт ошибку.
Тогда уже надо q.erase(q.find(...)).
Ну erase'у можно просто передавать значение, которое надо удалить, он сам сделает find. Так что какая ошибка выдаётся - не знаю.
И не знаю, почему только у тебя ТЛится, может, у тебя чтение медленное? Или делай break, когда из очереди достаётся вершина v, равная конечной. Ну и для пущего ускорения произведи избавление от pair в setе.
кстати, может и из-за чтения..
в общем, спасибо за совет, попробую так.
А лучше кучу сам пиши В этом будут только плюсы.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Dijkstra with Set