Find The City With The Smallest Number Of Neighbors At A Threshold Distance · Interview Problem

Back to problems

Leetcode

find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance

Medium

Graphs

Shortest Path

Floyd-Warshall

Dijkstra

Find The City With The Smallest Number Of Neighbors At A Threshold Distance

Find the city with the smallest number of neighbors reachable within a given distance threshold and return the city with the greatest index in case of ties.

Acceptance 100%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

You are given an integer n representing the number of cities numbered from 0 to n-1. You are also given an array edges where each edges[i] = [from_i, to_i, weight_i] represents a bidirectional weighted edge between cities from_i and to_i, and an integer distanceThreshold. A city is considered reachable from another city if the shortest distance between them is less than or equal to distanceThreshold. Your task is to find the city with the smallest number of reachable cities within the distance threshold. If there are multiple such cities, return the one with the greatest city number.

Input Format

An integer n, the number of cities.
A 2D integer array edges where each element is [from_i, to_i, weight_i].
An integer distanceThreshold.

Output Format

Return the city number which has the smallest count of reachable cities within the distanceThreshold. If multiple, return the city with the greatest number.

Constraints

2 <= n <= 100
1 <= edges.length <= n * (n-1) / 2
edges[i].length == 3
0 <= from_i, to_i < n
1 <= weight_i, distanceThreshold <= 10^4
There are no duplicate edges and no self-loops.

Loading Preptin

Description

Input Format

Output Format

Constraints