Roads and Libraries - Hackerrank Problem Solution in Python

Roads and Libraries

Hackerrank Problem Solution

Roads and Libraries - Hackerrank Problem Solution

PROBLEM STATEMENT

Determine the minimum cost to provide library access to all citizens of HackerLand. There are  cities numbered from  to . Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in . A citizen has access to a library if:

• Their city contains a library.
• They can travel by road from their city to a city containing a library.

Example

The following figure is a sample map of HackerLand where the dotted lines denote possible roads:

The cost of building any road is , and the cost to build a library in any city is . Build  roads at a cost of  and  libraries for a cost of . One of the available roads in the cycle  is not necessary.

There are  queries, where each query consists of a map of HackerLand and value of  and . For each query, find the minimum cost to make libraries accessible to all the citizens.

Function Description

Complete the function roadsAndLibraries in the editor below.
roadsAndLibraries has the following parameters:

• int n: integer, the number of cities
• int c_lib: integer, the cost to build a library
• int c_road: integer, the cost to repair a road
• int cities[m][2]: each  contains two integers that represent cities that can be connected by a new road

Returns
- int: the minimal cost

Input Format

The first line contains a single integer , that denotes the number of queries.

The subsequent lines describe each query in the following format:
- The first line contains four space-separated integers that describe the respective values of , ,  and , the number of cities, number of roads, cost of a library and cost of a road.
- Each of the next  lines contains two space-separated integers,  and , that describe a bidirectional road that can be built to connect cities  and .

Constraints

• Each road connects two distinct cities.

Sample Input

STDIN       Function
-----       --------
2           q = 2
3 3 2 1     n = 3, cities[] size m = 3, c_lib = 2, c_road = 1
1 2         cities = [[1, 2], [3, 1], [2, 3]]
3 1
2 3
6 6 2 5     n = 6, cities[] size m = 6, c_lib = 2, c_road = 5
1 3         cities = [[1, 3], [3, 4],...]
3 4
2 4
1 2
2 3
5 6

Sample Output

4
12

Explanation

Perform the following  queries:

1. HackerLand contains  cities and can be connected by  bidirectional roads. The price of building a library is  and the price for repairing a road is .
   

   The cheapest way to make libraries accessible to all is to:

   • Build a library in city  at a cost of .
   • Build the road between cities  and  at a cost of .
   • Build the road between cities  and  at a cost of .

   This gives a total cost of . Note that the road between cities  and  does not need to be built because each is connected to city .

2. In this scenario it is optimal to build a library in each city because the cost to build a library is less than the cost to build a road.
   

   There are  cities, so the total cost is .

---

SOLUTION IN PYTHON

#!/bin/python3 import math import os import random import re import sys # Complete the roadsAndLibraries function below. def DFSrec(adj,s,visited,val): visited[s] = 1 val += 1 for i in adj[s]: if visited[i]==0: val = DFSrec(adj,i,visited,val) return val def roadsAndLibraries(n, c_lib, c_road, cities): if c_road>c_lib: return n*c_lib else: adj = dict() for i in cities: if i[0] in adj: adj[i[0]].append(i[1]) else: adj[i[0]] = [i[1]] if i[1] in adj: adj[i[1]].append(i[0]) else: adj[i[1]] = [i[0]] for i in range(1,n+1): if i in adj: pass else: adj[i] = [] visited = [0]*(n+1) countNodes = 0 countComponents = 0 l = [] for i in range(1,n+1): if visited[i]==0: val = 0 nodes = DFSrec(adj,i,visited,val) countComponents += 1 l.append(nodes) total = 0 for i in l: total = total + (c_road*(i-1)) total = total + countComponents*c_lib return total if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') q = int(input()) for q_itr in range(q): nmC_libC_road = input().split() n = int(nmC_libC_road[0]) m = int(nmC_libC_road[1]) c_lib = int(nmC_libC_road[2]) c_road = int(nmC_libC_road[3]) cities = [] for _ in range(m): cities.append(list(map(int, input().rstrip().split()))) result = roadsAndLibraries(n, c_lib, c_road, cities) fptr.write(str(result) + '\n') fptr.close()

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.