Problem of the day
You are given ‘N’ cities numbered from 0 to N-1 and ‘M’ edges. These cities are connected with undirected weighted edges. You are also given a positive integer, ‘distanceThreshold’.
Your task is to find the ‘city’ to which the minimum number of cities are reachable through some path whose distance is no more than the given ‘distanceThreshold’.
Note:
1. If multiple such cities exist, you have to find the city with the greatest number.
2. The distance of a path connecting two cities, ‘U’ and ‘V’, is the sum of the weight of the edges along that path.
3. The distance between two cities is the minimum of all possible path distances.
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains three positive integers, ‘N’, ‘M’, and ‘distanceThreshold’, as described in the problem statement.
The next ‘M’ lines of each test case contain three integers, ‘U’, ‘V’, and ‘W’ each, representing each edge of the graph.
The edge U V W represents an edge between vertices ‘U’ and ‘V’, having weight ‘W’.
Note:
The ‘edges’ will be passed to the function as an array of arrays. Each array will contain three integers, ‘U’, ‘V’, and ‘W’ in that order.
Output Format:
For each test case, print a single line containing a single integer denoting the required ‘city’ number, as described in the problem statement.
The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10
2 <= N <= 100
1 <= M <= (N * (N - 1)) / 2
0 <= U, V < N
1 <= W, distanceThreshold <= 100
Where ‘T’ denotes the number of test cases, ‘N’ represents the number of cities, and ‘M’ denotes the number of edges.
‘U’, ‘V’, and ‘W’ denote the edge between city ‘U’ and ‘W’ having weight ‘W’.
Time limit: 1 sec.
1
5 5 3
0 1 1
1 2 1
2 3 3
3 4 1
0 3 3
4
The cities reachable to each city at a ‘distanceThreshold’ = 3 are as follows:
City 0 -> {City 1, City 2, City 3}
City 1 -> {City 0, City 2}
City 2 -> {City 0, City 1, CIty 3}
City 3 -> {City 0, City 2, City 3}
City 4 -> {City 3}
The city with the smallest number of neighbors at a ‘distanceThreshold’ = 3 is city 4 which has only 1 neighboring city.
1
3 3 4
0 1 2
1 2 2
2 0 1
2
The cities reachable to each city at a ‘distanceThreshold’ = 4 are as follows:
City 0 -> {City 1, City 2}
City 1 -> {City 0, City 2}
City 2 -> {City 0, City 1}
All three cities have 3 neighboring cities, So the answer must be the city with the greatest number that is city 2.
For each city calculate the number of reachable cities within the threshold, then search for the optimal city.
The idea here is to use Dijkstra’s algorithm to compute the distance between cities as the edge weights are non-negative. This algorithm fixed one node and treated it as a source and compute the distance of other nodes to the source. First, we need to make the adjacency list for the graph which contains for each city the city to which it is connected, and the edge weight of that edge. Now, we have to run Dijkstra’s algorithm for each city to find the distance of all other cities to it. Please read more about Dijkstra’s algorithm from Wikipedia.
Now, for each city, we have to calculate the reachable cities within the threshold. We can use the vector of pairs for the same, where the 1st element denotes the number of reachable cities to a particular city and the 2nd element represents the number of that city (that is used to break the tie). Sort the vector of pairs in a way that the 1st element of the vector will contain the desired output, and the second of the 1st element is the required city number.
O(N * (MlogN)), where ‘N’ is the number of cities, and ‘M’ is the number of edges.
The time complexity of Dijkstra’s Algorithm is ‘M * logN’, and in the worst-case ‘M’ will be (N * (N-1))/2. Since we are calling Dijkstra’s algorithm for all the cities from 0 to N. Hence, overall time complexity will be O(N * (MlogN)).
O(N ^ 2), where ‘N’ is the number of cities.
As we are creating an adjacency list for the graph, and in the worst case the graph will contain (N * (N - 1)) / 2 edges. Hence, we required an extra O(N ^ 2) space.