find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.cpp

// Time:  O(n^3)
// Space: O(n^2)

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> dist(n, vector<int>(n, numeric_limits<int>::max()));
        for (const auto& e : edges) {
            dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];
        }
        for (int i = 0; i < n; ++i) {
            dist[i][i] = 0;
        }
        for (int k = 0; k < n; ++k) {
             for (int i = 0; i < n; ++i) {
                 for (int j = 0; j < n; ++j) {
                     if (dist[i][k] != numeric_limits<int>::max() &&
                         dist[k][j] != numeric_limits<int>::max()) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                     }
                 }
             }
        }
        int result = -1, min_num = numeric_limits<int>::max();
        for (int i = n - 1; i >= 0; --i) {
            int num = accumulate(dist[i].cbegin(), dist[i].cend(), 0,
                                 [&distanceThreshold](const auto& a, const auto& b) {
                                     return a + (b <= distanceThreshold);
                                 });
            if (num < min_num) {
                min_num = num;
                result = i;
            }
        }
        return result;
    }
};