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

Правка ru1, от Infoshoc, 2021-01-22 16:53:43

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

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

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

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

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

История

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