The Quietest City Within Driving Range
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Explore Every Route From Every City
BruteFor each city, explore every route that never revisits a city, adding the road lengths, and keep the shortest length found to every other city. Count the cities whose shortest length is at most the threshold. Remember the city with the smallest count, letting later cities win ties. The exhaustive route search costs about n! per city.
O(n · n!)O(n)1class Solution {
2 private void explore(int[][] roads, int u, int total, boolean[] onPath, int[] best) {
3 best[u] = Math.min(best[u], total);
4 onPath[u] = true;
5 for (int v = 0; v < roads.length; v++) {
6 if (roads[u][v] > 0 && !onPath[v]) {
7 explore(roads, v, total + roads[u][v], onPath, best);
8 }
9 }
10 onPath[u] = false;
11 }
12
13 public int quietestCity(int[][] roads, int threshold) {
14 int n = roads.length;
15 int bestCity = 0;
16 int fewest = Integer.MAX_VALUE;
17 for (int city = 0; city < n; city++) {
18 int[] best = new int[n];
19 Arrays.fill(best, Integer.MAX_VALUE);
20 explore(roads, city, 0, new boolean[n], best);
21 int reachable = 0;
22 for (int j = 0; j < n; j++) {
23 if (j != city && best[j] <= threshold) reachable++;
24 }
25 if (reachable <= fewest) {
26 fewest = reachable;
27 bestCity = city;
28 }
29 }
30 return bestCity;
31 }
32}Optimal — Floyd–Warshall Distances, Then Count
OptimalCompute the shortest distance between every pair of cities with Floyd–Warshall: start from the road lengths (0 on the diagonal, infinity for missing roads) and, for every city k taken in turn as a middle stop, replace dist[i][j] by dist[i][k] + dist[k][j] whenever that is shorter. Then, for every city, count the other cities with distance at most the threshold, and pick the city with the smallest count, preferring the larger number on ties (use <= when comparing). Total O(n³).
O(n³)O(n²)1class Solution {
2 public int quietestCity(int[][] roads, int threshold) {
3 int n = roads.length;
4 int INF = 1_000_000;
5 int[][] dist = new int[n][n];
6 for (int i = 0; i < n; i++) {
7 for (int j = 0; j < n; j++) {
8 if (i == j) dist[i][j] = 0;
9 else dist[i][j] = roads[i][j] > 0 ? roads[i][j] : INF;
10 }
11 }
12 for (int k = 0; k < n; k++) {
13 for (int i = 0; i < n; i++) {
14 for (int j = 0; j < n; j++) {
15 if (dist[i][k] + dist[k][j] < dist[i][j]) {
16 dist[i][j] = dist[i][k] + dist[k][j];
17 }
18 }
19 }
20 }
21 int bestCity = 0;
22 int fewest = Integer.MAX_VALUE;
23 for (int city = 0; city < n; city++) {
24 int reachable = 0;
25 for (int j = 0; j < n; j++) {
26 if (j != city && dist[city][j] <= threshold) reachable++;
27 }
28 if (reachable <= fewest) {
29 fewest = reachable;
30 bestCity = city;
31 }
32 }
33 return bestCity;
34 }
35}