# Untitled

unknown
plain_text
8 days ago
1.6 kB
3
Indexable
Never
```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);
}
}
};```