Prims giving TLE for DAVIDG in spoj

I am trying the question DAVIDG in spoj. Problem link: SPOJ.com - Problem DAVIDG . I tried to solve the problem using prims algorithm which is giving TLE verdict. My code: 7nYL0W - Online C++ Compiler & Debugging Tool - Ideone.com .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: dhKuoe - Online C++ Compiler & Debugging Tool - Ideone.com which also got TLE verdict. Please someone help me in solving this problem.

1 Like