New update is available. Click here to update.

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

MEDIUM

15 mins

6 upvotes

Graph

Dynamic Programming

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

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

Contributed by

Yash_5830

Medium

0/80

Avg time to solve 15 mins

Success Rate 85 %

6 upvotes

Problem Statement

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.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format:

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.

Constraints:

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.

Sample Input 1:

Sample Output 1:

Explanation for sample input 1:

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.

Sample Input 2:

Sample Output 2:

Explanation for sample input 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.

Auto

Console