sunny_saraff's blog

By sunny_saraff, history, 4 months ago,

Problem-MARYBMW

**My Approach:- ** At first,I've created a maximum spanning tree from the given data using kruskal algorithmn, Again , i had found the shortest path from 1 to n and take the minimum edge weight which would be our ans as obvious. Everthing worked fine but getting Time Limit Exceeded(TLE). Please correct me if I am wrong in any of my approach

Link to My Code

Need Help..I am getting TLE on test 15 and can't figure out how can I make it faster. Any help would be appreciated.

• +1

 » 4 months ago, # |   0 Any help would be appreciated .dsjn;lm,'sa
 » 3 months ago, # | ← Rev. 2 →   +1 .
 » 3 months ago, # |   +3 Auto comment: topic has been updated by sunny_saraff (previous revision, new revision, compare).
 » 3 months ago, # |   +3 Auto comment: topic has been updated by sunny_saraff (previous revision, new revision, compare).
 » 3 months ago, # |   +4 Your disjoint set doesn't have either path compression, or union by rank/size. So each find/union operation can take O(n).Try: return parent[x] = find_set(parent[x],parent);
 » 3 weeks ago, # |   0 In your code, what is the use of finding maximum spanning tree ? You are just checking if node 0 and node n-1 are in the same connected component or not.When calculating the answer you just did a bfs on the original graph and not on the maximal spanning tree. Your approach is also wrong apart from TLE issues.