My implementation of Prim's is really slow.
So I searched up a fast way to do Prim's algorithm on geeksforgeeks.com, it is here: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/ It is O(V^2). It uses two disjoint sets and finds the minimum edges between them with an adjacency matrix.
But the website has a faster way: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/ It is O(ElogV). It uses an adjacency list and a priority_queue to speed up Prim's.
I understand the concept of Prim's, but my implementation is really slow.
It is O(V^3).
Here is the problem it applies to (very straight forward): http://www.spoj.com/problems/MST/ — I got AC my but my algorithm is very slow
How can I improve this implementation?