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

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

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

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