diff options
Diffstat (limited to 'find_city_smallest_neighbour.c')
-rw-r--r-- | find_city_smallest_neighbour.c | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/find_city_smallest_neighbour.c b/find_city_smallest_neighbour.c new file mode 100644 index 0000000..4bc95ef --- /dev/null +++ b/find_city_smallest_neighbour.c @@ -0,0 +1,56 @@ +// 1334. Find the City With the Smallest Number of Neighbors at a Threshold +// Distance +#include "leetcode.h" + +/* + * there are 'n' cities numbered from 0 to 'n - 1'. given the array 'edges' + * where 'edges[i] = [from_i, to_i, weight_i]' represents a bidirectional and + * weighted edge between cities 'from_i' and 'to_i' and given the integer + * 'distanceThreshold'. return the city with the smallest number of cities that + * are reachable through some path and whose distance is at most + * 'distanceThreshold', if there are multiple cities, return the city with the + * greatest number. notice that the distance of a path connecting cities i and j + * is equal to the sum of of the edges' weights along that path + */ + +int findTheCity(int n, int **edges, int edgesSize, int *edgesColSize, + int distanceThreshold) { + int ans = 0, min_reach = INT_MAX, dist[n][n]; + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) + dist[i][j] = 1e6; + dist[i][i] = 0; + } + for (int i = 0; i < edgesSize; i++) { + dist[edges[i][0]][edges[i][1]] = edges[i][2]; + dist[edges[i][1]][edges[i][0]] = edges[i][2]; + } + for (int k = 0; k < n; k++) + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + dist[i][j] = fmin(dist[i][j], dist[i][k] + dist[k][j]); + for (int i = 0; i < n; i++) { + int reachable = 0; + for (int j = 0; j < n; j++) { + if (dist[i][j] > distanceThreshold) + continue; + reachable++; + } + if (reachable > min_reach) + continue; + min_reach = reachable; + ans = i; + } + return ans; +} + +int main() { + int e1[4][3] = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}}, + e2[6][3] = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, + {1, 4, 2}, {2, 3, 1}, {3, 4, 1}}; + int ecs1 = 4, ecs2 = 6; + printf("%d\n", + findTheCity(4, (int **)e1, ARRAY_SIZE(e1), &ecs1, 4)); // expect: 3 + printf("%d\n", + findTheCity(5, (int **)e1, ARRAY_SIZE(e1), &ecs2, 2)); // expect: 0 +} |