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