Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Find the City With the Smallest Number of Neighbors at a Threshold Distance
MEDIUM
15 mins
6 upvotes
Graph
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Graph
-
-
Dynamic Programming
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
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.

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

Contributed by
Yash_5830
Medium
yellow-spark
0/80
Avg time to solve 15 mins
Success Rate 85 %
Share
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 )
Sample Input 1:
1
5 5 3
0 1 1
1 2 1
2 3 3
3 4 1
0 3 3
Sample Output 1:
4

altImage

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:
1
3 3 4
0 1 2
1 2 2
2 0 1
Sample Output 2:
2

altImage

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.
Reset Code
Full screen
Auto
copy-code
Console