leetcode

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 };