leetcode

0 class Solution {

1 typedef pair<int, int> edge;

2

3 public:

4 int networkDelayTime(vector<vector<int>> &times, int n, int k) {

5 vector<vector<edge>> adj(n + 1, vector<edge>());

6 for (auto &p : times)

7 adj[p[0]].push_back({p[2], p[1]});

8

9 priority_queue<edge, vector<edge>, greater<edge>> st;

10 unordered_set<int> us;

11

12 int time = 0;

13 st.push({0, k});

14 while (!st.empty()) {

15 auto [t, root] = st.top();

16 st.pop();

17 if (us.count(root)) continue;

18 time = t;

19 us.insert(root);

20 for (auto &[time, dest] : adj[root])

21 if (!us.count(dest)) st.push({t + time, dest});

22 }

23 return us.size() == n ? time : -1;

24 }

25 };