City With Smallest Number of Neighbors
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the city with the smallest number of other cities reachable within a threshold distance, with tie-breaker by largest city index., Graph, Weighted Graph, Shortest Path, All-Pairs Shortest Path, Adjacency Matrix, Floyd Warshall Algorithm, Dijkstra's Algorithm, Time Complexity, Space Complexity, Loops, Conditional Statements, Matrices, Optimization, graph representation, floyd-warshall algorithm, dijkstra's algorithm, shortest path algorithms, graph properties, tie-breaking, time complexity analysis, Graph Types, Shortest Path (Dijkstra's Algorithm).
Problem Statement: There are n cities numbered from 0 to n 1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold. You need to find out a city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold. If there are multiple such cities, the answer will be the city with the greatest number. Note : The distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path. Input Specification: n: An integer representing the number of cities. m: An integer representing the number of edges. edges: A 2D array where edges[i] = [fromi, toi, weighti] represents a bidirectional edge with a weight weighti between cities fromi and toi. distanceThreshold: An integer representing the maximum allowed distance to consider a city reachable. Output Specification: Return the integer representing the city number that satisfies the conditions. Constraints: Constraints were not explicitly provided in the original content. Sample Test Cases: Example 1: Input Format: Output: Explanation: The adjacent cities for each city at a distanceThreshold are: City 0 → [City 1, City 2] City 1 → [City 0, City 2, City 3] City 2 → [City 0, City 1, City 3] City 3 → [City 1, City 2] Here, City 0 and City 3 have a minimum number of cities i.e., 2 within distanceThreshold. So, the result will be the city with the largest number. Thus, the answer is City 3. Example 2: Input Format: Output: Explanation: City 1 → City 2 City 2 → City 1 Hence, 2 is the answer.