The Quietest City Within Driving Range

Implement quietestCity

A region has n cities connected by two-way roads of given lengths. A city is within range of another if the shortest route between them is at most a given distance. Find the city that has the fewest other cities within range; if there is a tie, choose the city with the largest number.

Computing all pairwise shortest distances with Floyd–Warshall reduces the problem to counting entries of the distance table.

Example 1:

Input: roads = [[0,3,0,0,0],[3,0,2,4,0],[0,2,0,1,0],[0,4,1,0,2],[0,0,0,2,0]], threshold = 4

Output: 0

Example 2:

Input: roads = [[0,5],[5,0]], threshold = 5

Output: 1

Example 3:

Input: roads = [[0,5],[5,0]], threshold = 4

Output: 1

+ 15 hidden test cases run on Submit.

Constraints:

  • ●1 ≤ n ≤ 7 cities numbered 0 … n-1; roads is a symmetric n × n matrix: roads[u][v] = 0 means no road between u and v, and roads[u][v] = w (1 ≤ w ≤ 20) means a two-way road of length w
  • ●roads[u][u] = 0; 0 ≤ threshold ≤ 60
  • ●A city is within range of another when the shortest route between them (possibly through other cities) has length at most threshold
  • ●Return the city that has the FEWEST other cities within range; if several cities tie, return the one with the largest number

roads =

[[0,3,0,0,0], [3,0,2,4,0], [0,2,0,1,0], [0,4,1,0,2], [0,0,0,2,0]]

threshold =

4