Untitled

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        unordered_map<int, unordered_map<int, int>> G;
        vector<pair<int, int>> neighbor;
        for (vector<int> &e : edges) {
            G[e[0]].emplace(e[1], e[2]);
            G[e[1]].emplace(e[0], e[2]);
        }
        for (auto &city : G) {
            bool cities[101]={false};
            int minThres[101]={0};
            dfs(G, city.first, distanceThreshold, cities, minThres);
            int count = 0;
            for (int i=0; i<101; ++i) {
                if (cities[i] == true)
                    count++;
            }
            neighbor.emplace_back(pair{city.first, count});
        }
        for (int i=0; i<n; ++i) {
            if (G.find(i) == G.end())
                neighbor.emplace_back(pair{i, 1});
        }
        auto cmp = [](const pair<int, int> &lhs, const pair<int, int> &rhs){
            return lhs.second < rhs.second || 
            (lhs.second == rhs.second && lhs.first > rhs.first);
        };
        sort(neighbor.begin(), neighbor.end(), cmp);
        return neighbor[0].first;
    }

    void dfs(unordered_map<int, unordered_map<int, int>> &G, int n, int thres, bool *cities, int *minThres) {
        if (thres < 0) return;
        cities[n] = true;
        minThres[n] = thres;
        for (auto &neighbor : G[n]) {
            if (minThres[neighbor.first] > thres-neighbor.second) continue;
            dfs(G, neighbor.first, thres-neighbor.second, cities, minThres);
        }
    }
};