Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from to 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities . 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. The cost of building any road is cc_road = 2 , and the cost to build a library in any city is c_lib = 3 . Build 5 roads at a cost of 5 * 2 = 10 and libraries for a cost of 6 . One of the available roads in the cycle is 1-> 2 -> 3 -> 1 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. -------------------------------------------------------------------------------------- Please implement the function 'roadsAndLibraries' in C #include #include #include #include #include #include #include #include #include #include char* readline(); char* ltrim(char*); char* rtrim(char*); char** split_string(char*); int parse_int(char*); /* * Complete the 'roadsAndLibraries' function below. * * The function is expected to return a LONG_INTEGER. * The function accepts following parameters: * 1. INTEGER n * 2. INTEGER c_lib * 3. INTEGER c_road * 4. 2D_INTEGER_ARRAY cities */ long roadsAndLibraries(int n, int c_lib, int c_road, int cities_rows, int cities_columns, int** cities) { } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); int q = parse_int(ltrim(rtrim(readline()))); for (int q_itr = 0; q_itr < q; q_itr++) { char** first_multiple_input = split_string(rtrim(readline())); int n = parse_int(*(first_multiple_input + 0)); int m = parse_int(*(first_multiple_input + 1)); int c_lib = parse_int(*(first_multiple_input + 2)); int c_road = parse_int(*(first_multiple_input + 3)); int** cities = malloc(m * sizeof(int*)); for (int i = 0; i < m; i++) { *(cities + i) = malloc(2 * (sizeof(int))); char** cities_item_temp = split_string(rtrim(readline())); for (int j = 0; j < 2; j++) { int cities_item = parse_int(*(cities_item_temp + j)); *(*(cities + i) + j) = cities_item; } } long result = roadsAndLibraries(n, c_lib, c_road, m, 2, cities); fprintf(fptr, "%ld\n", result); } fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } alloc_length <<= 1; data = realloc(data, alloc_length); if (!data) { data = '\0'; break; } } if (data[data_length - 1] == '\n') { data[data_length - 1] = '\0'; data = realloc(data, data_length); if (!data) { data = '\0'; } } else { data = realloc(data, data_length + 1); if (!data) { data = '\0'; } else { data[data_length] = '\0'; } } return data; } char* ltrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } while (*str != '\0' && isspace(*str)) { str++; } return str; } char* rtrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } char* end = str + strlen(str) - 1; while (end >= str && isspace(*end)) { end--; } *(end + 1) = '\0'; return str; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; } int parse_int(char* str) { char* endptr; int value = strtol(str, &endptr, 10); if (endptr == str || *endptr != '\0') { exit(EXIT_FAILURE); } return value; }
Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from to 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities
. 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.
The cost of building any road is cc_road = 2 , and the cost to build a library in any city is c_lib = 3 . Build 5 roads at a cost of 5 * 2 = 10 and libraries for a cost of 6 . One of the available roads in the cycle is 1-> 2 -> 3 -> 1 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.
--------------------------------------------------------------------------------------
Please implement the function 'roadsAndLibraries' in C
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images