1
class Solution {
2
 public:
3
  int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience) {
4
    int n = patience.size();
5
    vector<vector<int>> graph(n);
6
    vector<int> time(n, -1);
7

8
    for (auto x : edges) { // create adjacency list
9
      graph[x[0]].push_back(x[1]);
10
      graph[x[1]].push_back(x[0]);
11
    }
12

13
    queue<int> q;
14
    q.push(0);
15
    time[0] = 0;
16
    while (q.size()) {
17
      int node = q.front();
18
      q.pop();
19

20
      for (auto child : graph[node]) {
21
        if (time[child] == -1) {        // if not visited.
22
          time[child] = time[node] + 1; // calc time for child node
23
          q.push(child);
24
        }
25
      }
26
    }
27

28
    int res = 0;
29
    for (int i = 1; i < n; i++) {
30
      int extraPayload = (time[i] * 2 - 1) / patience[i];
31
      // extra number of payload before the first message arrive back to data
32
      // server. since a data server can only send a message before first
33
      // message arrives back." and first message arrives at time[i]*2. so
34
      // "(time[i]*2-1)"
35

36
      int lastOut =
37
          extraPayload * patience[i];     // find the last time when a data server sends a message
38
      int lastIn = lastOut + time[i] * 2; // this is the result for current data server
39

40
      res = max(res, lastIn);
41
    }
42

43
    // at "res" time the last message has arrived at one of the data servers.
44
    // so at res+1 no message will be passing between servers.
45

46
    return res + 1;
47
  }
48
};