Find the City With the Smallest Number of Neighbors at a Threshold Distance

Leetcode Problem:

• Find the City With the Smallest Number of Neighbors at a Threshold Distance

Summary

• Find the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold.

Approach

• The solution uses Floyd-Warshall algorithm to find the shortest path between all pairs of cities, then iterates through each city to count the number of cities that are reachable within the distanceThreshold
• The city with the smallest count that has the greatest number is returned.

Complexity

• O(n^3)

Explain

• The solution first initializes a 2D array dis to store the shortest distance between each pair of cities
• It then iterates through each edge in the edges array and updates the dis array
• After that, it uses Floyd-Warshall algorithm to find the shortest path between all pairs of cities
• Finally, it iterates through each city and counts the number of cities that are reachable within the distanceThreshold
• The city with the smallest count that has the greatest number is returned.

Solution Code:

class Solution {
public:
        int findTheCity(int n, vector>& edges, int distanceThreshold) {
        vector> dis(n, vector(n, 10001));
        int res = 0, smallest = n;
        for (auto& e : edges)
            dis[e[0]][e[1]] = dis[e[1]][e[0]] = e[2];
        for (int i = 0; i < n; ++i)
            dis[i][i] = 0;
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; ++j)
                if (dis[i][j] <= distanceThreshold)
                    ++count;
            if (count <= smallest) {
                res = i;
                smallest = count;
            }
        }
        return res;
    }
};