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.
A very easy implementation using DFS and "Divide and Conquer Approach"
!/bin/python3importmathimportosimportrandomimportreimportsys## Complete the 'roadsAndLibraries' function below.## The function is expected to return a LONG_INTEGER.# The function accepts following parameters:# 1. INTEGER n# 2. INTEGER c_lib# 3. INTEGER c_road# 4. 2D_INTEGER_ARRAY cities##Here we use the "Divide and Conquer" approach #to solve the subproblem for each disconnected componentdefroadsAndLibraries(n,c_lib,c_road,cities):# Write your code here#To store the graphadjacency_list=[[]foriinrange(n+1)]#Fill in the adjacency listforx,yincities:adjacency_list[x].append(y)adjacency_list[y].append(x)#The cost reqdtotal_cost=0#Tells if a city has been visited or notvisited=[Falseforiinrange(n+1)]#Depth First Searchdefdfs(u,adjacency_list,visited):visited[u]=True#Number of visited till nown_cities=1forvinadjacency_list[u]:if(visited[v]==False):n_cities+=dfs(v,adjacency_list,visited)returnn_citiesforuinrange(1,n+1):if(visited[u]==False):#Place a library in city 'v' and bulid the roads to the remaining cities#excluding cylces(min spanning tree due to equal weight edges) n_cities=dfs(u,adjacency_list,visited)cost1=((n_cities-1)*(c_road))+c_lib#In case , placing library at each city is beneficialcost2=n_cities*c_lib#Considering each disconnected component and summing up the costs total_cost+=min(cost1,cost2)returntotal_costif__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')q=int(input().strip())forq_itrinrange(q):first_multiple_input=input().rstrip().split()n=int(first_multiple_input[0])m=int(first_multiple_input[1])c_lib=int(first_multiple_input[2])c_road=int(first_multiple_input[3])cities=[]for_inrange(m):cities.append(list(map(int,input().rstrip().split())))result=roadsAndLibraries(n,c_lib,c_road,cities)fptr.write(str(result)+'\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
A very easy implementation using DFS and "Divide and Conquer Approach"