I changed the way ties are broken in the priority queue and got the execution time for n=10 from about 40 minutes to about 40 seconds.