Find the City With the Smallest Number of Neighbors at a Threshold Distance LeetCode solution in C++

1
class Solution {
2
 public:
3
  unordered_map<int, int> m;
4
  int findTheCity(int n, vector<vector<int>> &edges, int threshold) {
5
    vector<vector<pair<int, int>>> adj(n);
6
    for (auto x : edges) {
7
      adj[x[0]].push_back({x[1], x[2]});
8
      adj[x[1]].push_back({x[0], x[2]});
9
    }
10
    int ind = -1, ans = 1e8;
11
    for (int i = 0; i < n; i++) {
12
      queue<pair<int, int>> q;
13
      q.push({i, 0});
14
      vector<int> dis(n, 1e8);
15
      dis[i] = 0;
16
      while (!q.empty()) {
17
        int node = q.front().first;
18
        int wt = q.front().second;
19
        q.pop();
20
        for (auto x : adj[node]) {
21
          int node1 = x.first;
22
          int wt1 = x.second;
23
          if (wt + wt1 < dis[node1]) {
24
            dis[node1] = wt + wt1;
25
            q.push({node1, wt + wt1});
26
          }
27
        }
28
      }
29
      int c = 0;
30
      for (int i = 0; i < dis.size(); i++) {
31
        if (dis[i] <= threshold) {
32
          c++;
33
        }
34
      }
35
      if (c <= ans) {
36
        ans = c;
37
        ind = max(ind, i);
38
      }
39
    }
40
    return ind;
41
  }
42
};