We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
We have to calculate minimum distance between all the nodes.
1. First we built the MST using kruskal algo, and then
2. count the number of time each edge is used (using DFS traversal start from any vertex)
3. And then multiply the cost of the edge with it.
fromcollectionsimportdefaultdictn,m=map(int,input().split())edges=[]parent=[iforiinrange(n)]for_inrange(m):a,b,c=map(int,input().split())edges.append((a-1,b-1,c))deffind(i):whilei!=parent[parent[i]]:parent[i]=parent[parent[i]]i=parent[i]returnidefunion(x,y):p_x=find(x)p_y=find(y)parent[p_y]=p_xdefis_connected(x,y):p_x=find(x)p_y=find(y)returnp_x==p_y# build MSTtree=defaultdict(list)edges.sort(key=lambdax:x[2])fora,b,cinedges:ifnotis_connected(a,b):union(a,b)tree[a].append((b,c))tree[b].append((a,c))ans=[0]*(2*m)# Run DFS to count the number of times an edge is used# as weights of all edges is different, hence each weight maps to a particular childrendefdfs(src,p=-1):total=1forv,cintree[src]:ifv!=p:children=dfs(v,src)# children => nodes right to edge, n - children => nodes left to edgeans[c]+=(n-children)*childrentotal+=childrenreturntotaldfs(0)res=0foriinrange(len(ans)):res+=ans[i]*(1<<i)print(str(bin(res))[2:])
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Roads in HackerLand
You are viewing a single comment's thread. Return to all comments →
We have to calculate minimum distance between all the nodes. 1. First we built the MST using kruskal algo, and then 2. count the number of time each edge is used (using DFS traversal start from any vertex) 3. And then multiply the cost of the edge with it.