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.
the solution involves build the graph and then find the connected components
the mininum edges to connect all the nodes in a graph is the total of nodes - 1
the cost of the roads is the number of edges - 1 * cost of the road
And for each graph component we need to add a library
defdfs(visited,graph,node):ifnodenotinvisited:visited.add(node)forneighbouringraph[node]:dfs(visited,graph,neighbour)returnvisiteddefroadsAndLibraries(n,c_lib,c_road,cities):ifc_lib<=c_road:returnc_lib*n# build the graphgraph={}foriinrange(1,n+1):graph[i]=[]forcityincities:graph[city[0]].append(city[1])graph[city[1]].append(city[0])# split graphs into componentsgraph_components=set()fornodeinrange(1,n+1):graph_elements=dfs(set(),graph,node)ifgraph_elementsnotingraph_components:graph_components.add(frozenset(graph_elements))print(f"graph_components: {graph_components}")# calculate the costcost_road=0lib_cost=0foriingraph_components:cost_road+=c_road*(len(i)-1)lib_cost+=c_libprint(f"cost_road: {cost_road}, lib_cost: {lib_cost}")returncost_road+lib_cost
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
the solution involves build the graph and then find the connected components the mininum edges to connect all the nodes in a graph is the total of nodes - 1 the cost of the roads is the number of edges - 1 * cost of the road And for each graph component we need to add a library