leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1334.cpp (1702B)

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