Когда я был маленьким ребёнком я многому научился (через сайт) у e-maxx.(Orz).
Вчасности там есть пост про Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры для разреженных графов . Там сказано что priority_queue реализован через кучи, и имеет меньшую константу чем set который базируеться на КЧ-деревьях. Обьяснение внятное.
Я вернулся в длинного перерыва в СП и посмотрел на недавний Educational Codeforces Round 102 (рейтинговый для Див. 2) ради разогрева. Там была милая 1473E - Минимальный путь написання Neon которая требовала Алгоритм Дейксры. Я использовал priority_queue из моей заготовки 105061903 и получил ТЛ 61. Я чертыхнулся и начал оптимизировать. В результате я попробоваь решение на set-ах и получил АС 105066945. Вот изменения:
Почему Дейкстра на set-ах работает быстрее чем дейкста на priority_queue?
Uh, the two submission links are the same link. I thought that one of them was supposed to be TLE and the other is AC. Maybe link this one instead https://codeforces.com/contest/1473/submission/105061903
Reverse happened with demoralizer.His solution using set TLEed and priority queue worked. Here are submissions
With set(TLE): https://codeforces.com/contest/1473/submission/104326547
with pq (AC) : https://codeforces.com/contest/1473/submission/104327939
This only the internal set VS PQ constant changes. Usually, when one codes Dijkstra with sets the old distance is removed from the queue on the update, and some memory is saved.
Yes that's right. Priority Queue method can be made faster though — make a custom comparator which compares only the first element of the pair. (It improves the constant factor by a lot in the worst case)
You should check after popping if the current minimum distance to this node equals to the one popped, since a node can be popped multiple times if you use priority_queue and if you process each one it'll result in wasting a lot of time. For example, look at my code without checking 105069884 and with checking 104306045
Oh actually nvm you do that, then I don't know what causes your TLE.
He don't do it in a proper way: 105071086, without your comment I've never noticed this bug :)
Wow, and I lived with this bug in the template! Thanks a lot!
Yeah, I know this fill bro, some bugs are really hard to notice, they live in template even after N >> 1 AC submits. I've recently found bug it my Modular class: comment
This shows how bad it is to use pairs instead of classes with proper field names and comparator.
Auto comment: topic has been updated by Infoshoc (previous revision, new revision, compare).