Дейкстра на set-ах быстрее чем Дейкстра на priority_queue?

Revision ru1, by Infoshoc, 2021-01-22 16:53:43

Когда я был маленьким ребёнком я многому научился (через сайт) у e-maxx.(Orz).

Вчасности там есть пост про Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры для разреженных графов . Там сказано что priority_queue реализован через кучи, и имеет меньшую константу чем set который базируеться на КЧ-деревьях. Обьяснение внятное.

Я вернулся в длинного перерыва в СП и посмотрел на недавний Educational Codeforces Round 102 (рейтинговый для Див. 2) ради разогрева. Там была милая 1473E - Минимальный путь написання Neon которая требовала Алгоритм Дейксры. Я использовал priority_queue из моей заготовки 105066945 и получил ТЛ 61. Я чертыхнулся и начал оптимизировать. В результате я попробоваь решение на set-ах и получил АС 105066945. Вот изменения:

Почему Дейкстра на set-ах работает быстрее чем дейкста на priority_queue?

Tags алгоритм дейкстры, set, priority queue

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Infoshoc 2021-01-22 17:26:37 9
ru3 Russian Infoshoc 2021-01-22 17:26:18 10
en2 English Infoshoc 2021-01-22 17:14:53 6 Tiny change: 'sion:105066945] and got ' -> 'sion:105061903] and got '
ru2 Russian Infoshoc 2021-01-22 17:14:38 6 Мелкая правка: 'sion:105066945] и получи' -> 'sion:105061903] и получи'
ru1 Russian Infoshoc 2021-01-22 16:53:43 1316 Первая редакция перевода на Русский
en1 English Infoshoc 2021-01-22 16:47:25 1587 Initial revision (published)