Network Delay Time LeetCode solution in C++

1
class cmp {
2
 public:
3
  bool operator()(pair<int, int> &a, pair<int, int> &b) {
4
    return a.second > b.second;
5
  }
6
};
7

8
class Solution {
9
 public:
10
  int networkDelayTime(vector<vector<int>> &times, int n, int k) {
11
    vector<pair<int, int>> a[n];
12
    for (auto it : times) {
13
      a[it[0] - 1].push_back({it[1] - 1, it[2]});
14
    }
15

16
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
17
    vector<int> dist(n, 1e7);
18

19
    pq.push({k - 1, 0});
20

21
    vector<int> vis(n, 0);
22
    while (pq.size()) {
23
      auto curr = pq.top();
24
      pq.pop();
25

26
      int v = curr.first;
27
      int w = curr.second;
28

29
      if (vis[v]) continue;
30

31
      vis[v] = 1;
32
      dist[v] = w;
33
      for (auto it : a[v]) {
34
        if (vis[it.first] == 0) {
35
          pq.push({it.first, it.second + w});
36
        }
37
      }
38
    }
39

40
    int mx = INT_MIN;
41
    for (auto it : dist) mx = max(mx, it);
42

43
    if (mx >= 1e7) return -1;
44
    return mx;
45
  }
46
};