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

Hint - Floyd-Warshall Algorithm

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
    {
        // Initialize the distance matrix with a large number

        // Distance from each city to itself is zero

        // Set the distance for each edge in the graph

        // Floyd-Warshall algorithm to find shortest paths between all pairs of cities

        // To store the city with the minimum count of reachable cities
        // To store the minimum number of reachable cities

        // Iterate over each city to find the one with the fewest reachable cities within the threshold
        for ()
        {

            // Count how many cities are reachable within the distance threshold

            // Update the result if this city has fewer reachable cities
        }
        // Return the city with the fewest reachable cities
    }
};

• Floyd-Warshall Algorithm

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
    {
        vector<vector<int>> dist(n, vector<int>(n, 1e9 + 7));

        for (int i = 0; i < n; i++) dist[i][i] = 0;

        for (const auto& edge : edges)
        {
            int start = edge[0];
            int end = edge[1];
            int weight = edge[2];
            dist[start][end] = weight;
            dist[end][start] = weight;
        }

        for (int k = 0; k < n; ++k)
        {
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int cities = -1;
        int record = n + 1;
        for (int i = 0; i < n; ++i)
        {
            int count = 0;

            for (int j = 0; j < n; ++j)
            {
                if (dist[i][j] <= distanceThreshold) count++;
            }

            if (count <= record)
            {
                record = count;
                cities = i;
            }
        }
        return cities;
    }
};

• T: $O(V^3)$
• S: $O(V^2)$