# Roads and Libraries

# Roads and Libraries

+ 50 comments It's easy to overthink this one.

If the cost of a road is >= the cost of a library, just build a library at each node.

Otherwise, use DFS to get the number of nodes (ct) in each connected component. Put 1 library in each component, and the total per component cost is simply ct-1 (a road to connect to each node in the compomnent) * cost of a road + cost of one library.

You'll never put more than one library per component because once you're adding an additional node to a component, the cost of just building a road will always be cheaper than the cost of disconnecting the node (not building a road) and building a library instead.

+ 12 comments Spent 3 hours trying to figure out why mine failed half the tests.

Bigger variables. Bigger variables all over.

+ 5 comments Be careful about integer limitations! My java 8 solution:

HashMap<Integer, ArrayList<Integer>> cityMap = new HashMap<>(); int n = scan.nextInt(); int m = scan.nextInt(); int libraryCost = scan.nextInt(); int roadCost = scan.nextInt(); for (int i = 1; i <= n; i++) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(i); cityMap.put(i, list); } for (int a1 = 0; a1 < m; a1++) { int x = scan.nextInt(); int y = scan.nextInt(); ArrayList<Integer> list1 = cityMap.get(x); ArrayList<Integer> list2 = cityMap.get(y); if (list1 != list2) { list1.addAll(list2); list2.forEach(i -> cityMap.put(i, list1)); } } if (libraryCost < roadCost) System.out.println((long) n * libraryCost); else { long cost = 0; for (ArrayList<Integer> list : cityMap.values()) { int size = list.size(); if (size > 0) { cost += libraryCost; cost += (size - 1) * roadCost; list.removeIf(i -> true); } } System.out.println(cost); }

+ 6 comments my really short and concise solution :

def roadsAndLibraries(n, c_lib, c_road, cities): if c_lib < c_road: return c_lib * n g, seen, ans = ddict(set), set(), 0 for i,j in cities: g[i].add(j) g[j].add(i) def dfs(i): seen.add(i) return sum(dfs(j) for j in g[i] if j not in seen) + 1 return sum((dfs(i) - 1) * c_road + c_lib for i in range(1, n + 1) if i not in seen)

+ 2 comments If a road is not cheaper than a library you don't even need to build the graph and can just ignore the roads data. Otherwise, all you need to know is the number of connected components. And, btw, why do they use dollars in HackerLand? Don't they have their own currency?

Sort 768 Discussions, By:

Please Login in order to post a comment