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

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)$