Prims giving TLE for DAVIDG in spoj

I am trying the question DAVIDG in spoj. Problem link: http://www.spoj.com/problems/DAVIDG/ . I tried to solve the problem using prims algorithm which is giving TLE verdict. My code: http://ideone.com/7nYL0W .The time constraints are really strict. Even after using fast io the time limit is exceeded. Another attempt to solve the problem was trying to reduce the number of edges of the graph by excluding edges which surely will not be in the MST. The code with the optimisation: http://ideone.com/dhKuoe which also got TLE verdict. Please someone help me in solving this problem.

1 Like
//