# Roads and Libraries

# Roads and Libraries

+ 1 comment Does anyone know why the

**“Sample Test Case #2”**came up with a minimum cost of 15? I got a smaller value of 9.The cities and roads configuration is:

L=6 +---+ | 1 | +---+ / | \ / | \ /R=1 |R=1 \R=1 +---+ +---+ +---+ | 2 | | 3 | | 4 | +---+ +---+ +---+

A library for 6 at city #1 and a road, at the cost of 1, to cities #2, #3, and #4; totaling 9.

How did they get 15?

+ 0 comments Here's in JS, with added comments and descriptive variable names to assist.

function roadsAndLibraries(n, c_lib, c_road, cities) { let spent = 0; let connects = new Map(); let visited = new Map(); const unvisited = []; const regions = []; // Populate connections and build out unvisited stack; cities.forEach(city => { const cityInd = city[0]; const dest = city[1]; unvisited.push(cityInd); connects.set(cityInd, connects.has(cityInd) ? [...connects.get(cityInd), dest] : [dest]); connects.set(dest, connects.has(dest) ? [...connects.get(dest), cityInd] : [cityInd]); }); // recursive visitation, returns self and further explores connected unvisited cities const visit = (current) => { if(!visited.has(current)) { visited.set(current, true); let currentRegion = [current]; const neighs = connects.get(current); neighs.forEach((n) => { currentRegion = [...currentRegion, ...visit(n)]; }); return currentRegion; } return []; }; // visits each node, if already visited in a preceeding exploration session, // skip, as already in established region, otherwise begin building out a new region. while(unvisited.length > 0) { const current = unvisited.pop(); if(!visited.has(current)) { regions.push(visit(current)); } } // Fill out cost of unconnected cities, i.e. cities which weren't given any neighbours in the input. // These all will be solo cities with their own library. for(let i = 1; i <= n; i++) { if(!connects.has(i)) { spent += c_lib; } } // Fill out the best case for each region, between one of two options, // either every city with their own library, or one library and all cities connected by one road to another. regions.forEach(r => { const costOfAllLibrary = c_lib * r.length; const costOfOneLibraryWithRoads = c_lib + (r.length - 1) * c_road; spent += Math.min(costOfAllLibrary, costOfOneLibraryWithRoads); }); return spent; }

+ 0 comments The shortest solution I was able to create:

def roadsAndLibraries(n, c_lib, c_road, cities): # Write your code here if c_road>c_lib: return n*c_lib conns = defaultdict(set) for i in range(n): conns[i+1]=set() for i in range(len(cities)): conns[cities[i-1][0]].add(cities[i-1][1]) conns[cities[i-1][1]].add(cities[i-1][0]) conns = dict(sorted(conns.items(), key=lambda item: -len(item[1]))) lens = [] for c in conns: lens.append(len(conns[c])) unvisited=set(range(1,n+1)) cost=0 while unvisited: current = unvisited.pop() cost+=c_lib connected = set(conns[current]) while (connected): nb = connected.pop() if nb in unvisited: unvisited.remove(nb) for i in conns[nb]: connected.add(i) cost+=c_road return cost

`co return cost`

+ 0 comments void insertCityToMap(std::map<long, vector<long>> &cityMap, int &cityNum1, int &cityNum2){ std::map<long, vector<long>>::iterator it = cityMap.find(cityNum1); if(it == cityMap.end()){ //insert new vector cityMap.insert(pair<long, vector<long>>(cityNum1, vector<long>{cityNum2})); }else{ if(find(it->second.begin(), it->second.end(), cityNum2) == it->second.end()) //sanity check incase of duplicate it->second.push_back(cityNum2); } } //arguments passed by reference void cityDfs(std::map<long, vector<long>> &cityMap, long &adj, std::vector<bool> &visited, long &minCost, int &c_road, int &count){ minCost += c_road; visited[adj] = true; count++; std::map<long, vector<long>>::iterator it = cityMap.find(adj); std::vector<long> connectedCities = it->second; for(long long i=0; i<connectedCities.size(); i++){ if(visited[connectedCities[i]] == false){ cityDfs(cityMap, connectedCities[i], visited, minCost, c_road, count); } } } long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) { if(c_lib <= c_road){ return long(c_lib*n); } std::map<long, vector<long>> cityMap; std::vector<bool> visited(n+1, false); for(long i=0; i<cities.size(); i++){ insertCityToMap(cityMap, cities[i][0], cities[i][1]); insertCityToMap(cityMap, cities[i][1], cities[i][0]); } std::map<long, vector<long>>::iterator it; long minCost = 0; int count = 0; //to track the number of visted cities. This will help when identifying the number of standalone cities. //starting with a map node (city), it will build one library and DFS to complete the rest of the sub-map. for(it=cityMap.begin(); it != cityMap.end(); it++){ if(visited[it->first] == false){ minCost += c_lib; visited[it->first] = true; count++; for(long long j=0; j < it->second.size(); j++){ if(visited[it->second[j]] == false){ cityDfs(cityMap, it->second[j], visited, minCost, c_road, count); } } } } return minCost+c_lib*(n-count); }

- build the map based on the cities info.
- iterate the map city by city, check the connected cities, and properly build the library and the roads for a complete sub map.
- iterate the rest of the map and complete the algorithm.

Mine passes 0, 1, 2, 7, 11, 12. The rest test cases with a huge input FAIL with wrong output. Not the time limit exceed. Could anyone provide a hint what I might be missing? Much appreciated! Thanks

+ 0 comments Be careful with those debug prints! I just found out:

1) A bug in iostream causing an infinite loop in one of my statements writing to cout 2) Obviously they kill your program after so much time has passed, and the printing slows it down, obviously. There is not way to distinguish this from a wrong result.

Sort 861 Discussions, By:

Please Login in order to post a comment