# Roads and Libraries

# Roads and Libraries

+ 0 comments Beaware of int32 overflow (non python users)

+ 0 comments Really nice problem! However, I rerun the test that failed with TLE, and it passed... Strange :(

**Hint alert**: the price is a sum of all subprices for every component, such that the price of the component is the min((number of nodes in component) * (library price), ((number of nodes in component minus one - spanning tree edges)* (road price) + (library price))

+ 0 comments Start out by making an adjacency list from the cities array, any cities not in the array will be considered a 'component'. A component is a group of connected nodes in an undirected graph. Find the number of components using DFS. The number of roads will be equal to the number of cities - number of components. Every component will need one library.

if c_lib <= c_road: return c_lib * n adj = collections.defaultdict(list) for start, des in cities: adj[start].append(des) adj[des].append(start) components = 0 def dfs(city, visited): if city in visited: return visited.add(city) for nei in adj.get(city,[]): dfs(nei, visited) visited = set() for i in range(1,n+1): if i not in visited: components += 1 dfs(i, visited) res = ((n-components) * c_road) + (c_lib * components) return res

+ 0 comments # > * https://)****

+ 0 comments Simple C++ solution using BFS.

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) { if (c_lib <= c_road) return (long)n * (long)c_lib; unordered_map<int, vector<int>> cities_map(cities.size() * 2); for (auto& c : cities) { cities_map[c[0]].push_back(c[1]); cities_map[c[1]].push_back(c[0]); } long total_cost = 0; queue<int> qu; vector<char> visited(n+1, 0); for (int i = 1; i <= n; i++) { if (!visited[i]) { total_cost += (long)c_lib; visited[i] = 1; qu.push(i); while(!qu.empty()) { int city = qu.front(); qu.pop(); for (int other : cities_map[city]) { if (!visited[other]) { total_cost += (long)c_road; qu.push(other); visited[other] = 1; } } } } } return total_cost; }

Sort 820 Discussions, By:

Please Login in order to post a comment