Roads in HackerLand
John lives in HackerLand, a country with cities and bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., raised to some exponent). It's possible for John to reach any city from any other city.
Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.
Input Format
The first line contains two space-seperated integers denoting (the number of cities) and (the number of roads), respectively.
Each line of the subsequent lines contains the respective values of , , and as three space-separated integers. These values define a bidirectional road between cities and having length .
Constraints
- ,
- If , then .
Output Format
Find the sum of minimum distances of each pair of cities and print the answer in binary representation.
Sample Input
5 6
1 3 5
4 5 0
2 1 3
3 2 1
4 3 4
4 2 2
Sample Output
1000100
Explanation
In the sample, the country looks like this:
Let be the minimum distance between city and city .
xxxxxxxxxxchar* readline();char* ltrim(char*);char* rtrim(char*);char** split_string(char*);int parse_int(char*);/* * Complete the 'roadsInHackerland' function below. * * The function is expected to return a STRING. * The function accepts following parameters: * 1. INTEGER n * 2. 2D_INTEGER_ARRAY roads *//* * To return the string from the function, you should either do static allocation or dynamic allocation * * For example, * char* return_string_using_static_allocation() { * static char s[] = "static allocation of string"; * * return s; * } * * char* return_string_using_dynamic_allocation() { * char* s = malloc(100 * sizeof(char)); * * s = "dynamic allocation of string"; * * return s; * } * */char* roadsInHackerland(int n, int roads_rows, int roads_columns, int** roads) {}int main(){ FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); 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** roads = malloc(m * sizeof(int*)); for (int i = 0; i < m; i++) { *(roads + i) = malloc(3 * (sizeof(int))); char** roads_item_temp = split_string(rtrim(readline())); for (int j = 0; j < 3; j++) { int roads_item = parse_int(*(roads_item_temp + j)); *(*(roads + i) + j) = roads_item; } } char* result = roadsInHackerland(n, m, 3, roads); fprintf(fptr, "%s\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;}