Given N cities numbered from 0 to N-1, an array of bidirectional weighted roads [first, second, weight], and a positive distanceThreshold, count the other cities reachable from every city with shortest-path distance at most the threshold.
Every road has a positive weight. Positive road weights ensure that Dijkstra’s Algorithm and threshold-based pruning remain valid.
Return the city having the smallest reachable-city count. Return the greatest city index when multiple cities share the minimum count.
Example 1
Input: N = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: Cities 0 and 3 each reach two other cities within the threshold. The greater tied index is 3.
Example 2
Input: N = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: City 0 reaches only city 1, producing the unique minimum count of one.
Approach 1
Floyd–Warshall computes shortest distances between every ordered pair of cities in a single matrix. A small city count makes cubic all-pairs processing practical, while the completed matrix supports direct threshold counting.
Cities are checked in ascending index order. Updating the answer for an equal reachable-city count ensures selection of the greatest city index.
Algorithm
Initialize an
N×Ndistance matrix with infinity and set every diagonal entry to0.Store each undirected road in both matrix directions, retaining the minimum weight when multiple roads connect the same city pair.
Run Floyd–Warshall using an outer loop for intermediate cities and inner loops for source and destination cities.
Skip a transition when either required segment remains unreachable, preventing invalid infinity calculations.
Update each source-to-destination distance with the smaller of the existing value and the route passing through the intermediate city.
For every source city, count all other cities having a shortest distance less than or equal to the threshold.
Update the answer when the count is smaller than or equal to the best count, then return the final city index.
Dry Run
find-the-city-floyd-warshall-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the greatest-index city among minimum reachable counts. int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) { const int INF = 1000000000; vector<vector<int>> dist(n, vector<int>(n, INF)); // Set every zero-length self distance. for (int city = 0; city < n; city++) { dist[city][city] = 0; } // Build the symmetric direct-distance matrix. for (const vector<int>& edge : edges) { int first = edge[0]; int second = edge[1]; int weight = edge[2]; dist[first][second] = min(dist[first][second], weight); dist[second][first] = min(dist[second][first], weight); } // Allow each city as an intermediate vertex. for (int middle = 0; middle < n; middle++) { for (int source = 0; source < n; source++) { for (int destination = 0; destination < n; destination++) { // Skip a route containing an unreachable segment. if (dist[source][middle] == INF || dist[middle][destination] == INF) { continue; } dist[source][destination] = min( dist[source][destination], dist[source][middle] + dist[middle][destination] ); } } } int bestCount = n; int answer = -1; // Count threshold-reachable neighbors for every city. for (int city = 0; city < n; city++) { int count = 0; for (int neighbor = 0; neighbor < n; neighbor++) { if (neighbor != city && dist[city][neighbor] <= distanceThreshold) { count++; } } // Replace equal counts to preserve the greatest index. if (count <= bestCount) { bestCount = count; answer = city; } } return answer; }};// Driver code.int main() { int n = 4; vector<vector<int>> edges = { {0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1} }; Solution sol; cout << sol.findTheCity(n, edges, 4); return 0;}Complexity Analysis
Time Complexity: O(N×N×N), where N is the number of cities; all intermediate, source, and destination combinations are processed.
Space Complexity: O(N×N), where the all-pairs distance matrix stores one shortest distance for every ordered city pair.
Approach 2
Positive road weights allow Dijkstra’s Algorithm to run independently from every source city. An adjacency list avoids an all-pairs matrix and improves efficiency for sparse graphs.
Routes exceeding the threshold require no further expansion because additional positive edges cannot reduce the distance. Processing cities in ascending order with equal-count replacement preserves the greatest index.
Algorithm
Build an undirected weighted adjacency list, storing every road in both directions.
Initialize
bestCountas infinity and traverse every city in ascending order as a Dijkstra source.For each source, initialize all distances as infinity, set the source distance to
0, and insert the source into a min-heap.Remove minimum-distance states, skip stale entries, stop when the smallest distance exceeds the threshold, and count every finalized city except the source.
Relax an adjacent edge only when the candidate distance is smaller and does not exceed the threshold, avoiding irrelevant heap states.
Update
bestCountand the answer when the current reachable-city count is smaller than or equal to the best count.Return the final answer after all source cities have been processed.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the greatest-index city among minimum reachable counts. int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) { vector<vector<pair<int, int>>> adj(n); // Build the undirected weighted adjacency list. for (const vector<int>& edge : edges) { int first = edge[0]; int second = edge[1]; int weight = edge[2]; adj[first].push_back({second, weight}); adj[second].push_back({first, weight}); } int bestCount = n; int answer = -1; // Run threshold-limited Dijkstra from every city. for (int source = 0; source < n; source++) { vector<int> dist(n, INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap; dist[source] = 0; minHeap.push({0, source}); int count = 0; // Process reachable cities in increasing distance. while (!minHeap.empty()) { auto [currentDistance, city] = minHeap.top(); minHeap.pop(); // Skip an entry replaced by a shorter route. if (currentDistance != dist[city]) { continue; } // Stop after crossing the allowed threshold. if (currentDistance > distanceThreshold) { break; } if (city != source) { count++; } // Relax every adjacent road within the threshold. for (const auto& [neighbor, weight] : adj[city]) { int candidate = currentDistance + weight; if (candidate <= distanceThreshold && candidate < dist[neighbor]) { dist[neighbor] = candidate; minHeap.push({candidate, neighbor}); } } } // Replace equal counts to preserve the greatest index. if (count <= bestCount) { bestCount = count; answer = source; } } return answer; }};// Driver code.int main() { int n = 4; vector<vector<int>> edges = { {0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1} }; Solution sol; cout << sol.findTheCity(n, edges, 4); return 0;}Complexity Analysis
Time Complexity: O(N×(N+E)×log N), where N is the number of cities and E is the number of roads; Dijkstra runs once from every city.
Space Complexity: O(N+E), where the adjacency list stores the graph, while the distance array and min-heap store one Dijkstra traversal.
Interview follow-up Questions
The task counts neighboring cities, while the zero-distance source is not a neighbor.
Be the first to add a comment.