1334.cpp (1702B)
1 class Solution { 2 struct edge { 3 int index, weight; 4 edge(int i, int w) : index(i), weight(w) {} 5 friend bool operator<(const edge &e1, const edge &e2) { return e1.weight > e2.weight; } 6 }; 7 8 int dijkstra(int n, vector<vector<edge>> &adj, int start, int threshold) { 9 vector<int> d(n, INT_MAX); 10 vector<bool> s(n, false); 11 priority_queue<edge> pq; 12 13 for (auto &p : adj[start]) { 14 d[p.index] = p.weight; 15 pq.push(p); 16 } 17 18 s[start] = true; 19 for (int k = 1; k < n; k++) { 20 while (!pq.empty() && s[pq.top().index]) 21 pq.pop(); 22 if (pq.empty()) break; 23 auto e = pq.top(); 24 pq.pop(); 25 s[e.index] = true; 26 for (auto &p : adj[e.index]) 27 if (!s[p.index] && d[e.index] + p.weight < d[p.index]) { 28 d[p.index] = d[e.index] + p.weight; 29 pq.push({p.index, d[p.index]}); 30 } 31 } 32 33 int count = 0; 34 for (int i = 0; i < n; i++) 35 count += d[i] <= threshold; 36 return count; 37 } 38 39 public: 40 int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) { 41 vector<vector<edge>> adj(n, vector<edge>()); 42 for (auto &p : edges) { 43 adj[p[0]].push_back({p[1], p[2]}); 44 adj[p[1]].push_back({p[0], p[2]}); 45 } 46 47 int res = -1; 48 for (int i = 0, mini = INT_MAX; i < n; i++) { 49 int tmp = dijkstra(n, adj, i, distanceThreshold); 50 if (tmp <= mini) { 51 mini = tmp; 52 res = i; 53 } 54 } 55 return res; 56 } 57 };