I solved this problem http://mirror.codeforces.com/contest/449/problem/B using dijkstra based on priority queue and I got TLE (http://mirror.codeforces.com/contest/449/submission/13186398) on test 45. After that I changed it to TreeSet ( http://mirror.codeforces.com/contest/449/submission/13186483 ) and it runs ~940ms instead of > 2000ms . What is wrong with my previous solution ? I read that priority queue runs faster in practice and I saw that most java solutions use priority queue
Priority queue doesn't work in Dijkstra when you store only indices in it, try to think why.
it does: 13187441
When the distance to some vertex is changed, this vertex doesn't change its position in the priority queue, while it should to maintain the heap property value(parent) <= value(child). So it's just weak tests.
CountZero has defined a custom comparison for the PriorityQueue and ignores vertices already visited so it is fundamentally correct.
EDIT: Have a look at the analysis
lol, no. Now I see dalex is right. Take a closer look at my code — there are no guarantees for heap property to be maintained. Anyway, we can implement Dijkstra algorithm using priority queue and custom comparator — we need a custom priority queue with method "delete any element".
Understood my mistake. Please ignore.
Of course it's correct, they store pairs (vertex, distance).
Thanks, I understand now.
BTW, you don't need 'delete any element' in priority-queue.
You can store a pair <vertex,distance(vertex)> in the priority-queue.