Problem Details

Find the City With the Smallest Number of Neighbors at a Threshold Distance

New update is available. Click here to update.

Last Updated: 18 Mar, 2021

Difficulty: Moderate

```
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’.
```

```
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.
```

```
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.
```

```
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.
```

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.

- Create a vector of pair of size
**N**named**adj**for the adjacency list. - Run a loop from i = 0 to edges.size(), in each iteration:
- Add {edges[i][1], edges[i][2]} in the adj[edges[i][0]].
- Add {edges[i][0], edges[i][2]} in the adj[edges[i][1]].

- Create a vector of pair named
**ans**, where 1st element denotes the number of reachable cities to a particular city and 2nd element represents the number of that city. - Run a loop with variable
**i**= 0 to**N**, in each iteration:- Call
**dijkstra**(i, N, adj, distanceThreshold, ans), where**i**is the current city,**N**is the number of cities,**adj**is the adjacency list,**distanceThreshold**is the given value, and**ans**is the vector of pair for storing the answer. - This function will update
**ans**with the number of cities reachable to city**i**.

- Call
**Sort**the vector ans with the help of the**compare**.- Finally, return
**ans[0].second**.

- This function is used to sort the vector of pairs.
- If
**x.firs**t !=**y.first**, then**return**x.first < y.first. - Return
**x.second**>**y.second**, because to break the tie we need the city with the greatest number first.

- This function is computing distance between
**src**and all other cities. - Create a HashSet of type
**pair**named**findDist**, where the**1st**element denotes the distance between**src**and the**city**whose id is in the**2nd**element. - Create a
**distance**array of size**N**, and initialize it with**INT_MAX**. - Set distance[
**src**] = 0, and insert {0, src} into the set. - Run a while loop until
**findDist**becomes empty, in each iteration:- Declare a variable
**v**, and initialize it with the**second**element of the**top**. - Remove the top element.
- Run a loop to find all the direct connections of
**v**, let**u**be its direct connections, and**w**be the edge weight in each iteration:- If distance[
**u**] > distance[**v**] +**w**, then update distance[**u**] = distance[**v**] +**w**, and**insert**{distance[u], u} into the set**findDist**.

- If distance[

- Declare a variable
- Declare a variable
**cnt**= 0. - Run a loop from
**i**= 0 to**N**, in each iteration:- If
**i**!=**src**and distance[**i**] <=**distanceThreshold**, then increase**cnt**by 1.

- If
- Add {cnt, i} into the vector of pairs
**ans**.

The idea here is to compute the distance between all pairs of cities. We can use **Floyd - Warshell’s **algorithm for the same. We first create a matrix named **distance **that will contain the distance between any two cities. Initialize the distance matrix with the edge weight which we have been provided directly. ** **We then update the distance matrix by considering all the **intermediate** vertices. Please read more about Floyd-Warshell’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 1st element denotes the number of reachable cities to a particular city and 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.

- Create a matrix named
**distance**of size**N**x**N**, and initialize it with a big integer,**INT_MAX**. - Call the function
**floydWarshells()**and pass an array of arrays named**edges**,**distance**matrix, and an integer**N**denoting the number of cities. - The above function updated the matrix
**distance**with the distance between all pairs of cities. - Create a vector of pair named
**ans**, where 1st element denotes the number of reachable cities to a particular city and 2nd element represents the number of that city. - Run a loop with variable
**i**= 0 to**N**, in each iteration:- Declare a variable named
**cnt**= 0. - Run a loop from
**j**= 0 to**N**, in each iteration:- If distance[
**i**][**j**] <=**distanceThreshold**, then increase**cnt**by 1.

- If distance[
- Push {cnt,i} into the vector
**ans**.

- Declare a variable named
**Sort**the vector ans with the help of the**compare**.- Finally, return
**ans[0].second**.

- This function is used to sort the vector of pairs.
- If
**x.firs**t !=**y.first**, then**return**x.first < y.first. - Return
**x.second**>**y.second**, because to break the tie we need the city with the greatest number first.

- This function is computing distance between all pairs of cities.
- Run a loop from
**i**= 0 to**i**=**edges**.size():- Update entries in the distance matrix with the given edge weights,
- distance[
**edges**[**i**][**0**]][**edges**[**i**][**1**]] =**edges**[**i**][**2**] - distance[
**edges**[**i**][**1**]][edges[**i**][**0**]] =**edges**[**i**][**2**]

- distance[

- Update entries in the distance matrix with the given edge weights,
- Now, update the distance matrix by considering all the intermediate nodes.
- Run a loop from
**k**= 0 to**N**, in each iteration:- Run a loop from
**i**= 0 to**N**, in each iteration:- Run a loop from
**j**= 0 to**N**, in each iteration:**distance**[**i**][**j**] =**min**(distance[**i**][**j**], distance[**i**][**k**] + distance[**k**][**j**]).

- Run a loop from

- Run a loop from

SIMILAR PROBLEMS

NINJA AND HAPPINESS

Posted: 9 Sep, 2022

Difficulty: Hard

DECODE STRING

Posted: 11 Sep, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: