Тема: Dijkstra with Set
Кто может реализовать дейкстру с set-ом на с++?
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
Re: Dijkstra with Set
Декстра с set-ом: http://e-maxx.ru/algo/dijkstra_sparse
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
Не совсем понял, Дейксра с Фенвиком? Такого алгоритма вроде нет. Если интересует просто дерево Фенвика, то вам сюда http://e-maxx.ru/algo/fenwick_tree
test
Re: Dijkstra with Set
Не совсем понял, Дейксра с Фенвиком? Такого алгоритма вроде нет. Если интересует просто дерево Фенвика, то вам сюда http://e-maxx.ru/algo/fenwick_tree
Судя по всему, aza_inf имел ввиду применение Фенвика для поиска минимального элемента в массиве для алгоритма Дейкстры. 
Re: Dijkstra with Set
Сомневаюсь, что Фенвиком можно это сделать: он умеет искать минимумы, только когда значения невозрастают в процессе апдейтов. В Дейкстре же надо иногда извлекать минимумы, т.е. фактически присваивать их бесконечности. Если кто-то представляет, как для этого применить Фенвика - буду благодарен, если объяснят 
Re: Dijkstra with Set
странно, но уже второй раз я пишу дейкстру с сетом как на е-максе и она ТЛится, хотя у остальных проходит( причем там вроде как ошбка - q.erase(make_pair(d[to], to)). должно быть ведь q.erase(find(make_pair(d[to], to))), но так он выдаёт ошибку.
Re: Dijkstra with Set
Тогда уже надо q.erase(q.find(...)).
Re: Dijkstra with Set
Ну erase'у можно просто передавать значение, которое надо удалить, он сам сделает find. Так что какая ошибка выдаётся - не знаю.
И не знаю, почему только у тебя ТЛится, может, у тебя чтение медленное? Или делай break, когда из очереди достаётся вершина v, равная конечной. Ну и для пущего ускорения произведи избавление от pair в setе.
8 2010-06-14 10:52:33 Отредактировано rembo (2010-06-14 10:53:57)
Re: Dijkstra with Set
кстати, может и из-за чтения..
в общем, спасибо за совет, попробую так.
Re: Dijkstra with Set
А лучше кучу сам пиши В этом будут только плюсы.