1
class Solution {
2
  public int networkBecomesIdle(int[][] edges, int[] patience) {
3
    int n = patience.length;
4

5
    // creating adjacency list
6
    ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
7
    for (int i = 0; i < n; i++) {
8
      adj.add(new ArrayList<>());
9
    }
10

11
    for (int[] edge : edges) {
12
      adj.get(edge[0]).add(edge[1]);
13
      adj.get(edge[1]).add(edge[0]);
14
    }
15

16
    // getting the distance array using dijkstra algorithm
17
    int[] dist = dijkstra(adj);
18

19
    // variable to store the result
20
    int ans = 0;
21

22
    // performing the calculations discussed above for each index
23
    for (int x = 1; x < n; x++) {
24

25
      // round trip time
26
      int time = 2 * dist[x];
27

28
      int p = patience[x];
29

30
      // total number of messages the station will send until it receives the reply of first message
31
      int numberOfMessagesSent = (time) / p;
32

33
      // handling an edge case if round trip time is a multiple of patience example time =24
34
      // patience = 4
35
      // then the reply would be received at 24 therefore station will not send any message at t =
36
      // 24
37
      if (time % p == 0) {
38
        numberOfMessagesSent--;
39
      }
40

41
      // time of last message
42
      int lastMessage = numberOfMessagesSent * p;
43

44
      // updating the ans to store max of time at which the station becomes idle
45
      ans = Math.max(ans, lastMessage + 2 * dist[x] + 1);
46
    }
47

48
    return ans;
49
  }
50

51
  // simple dijkstra algorithm implementation
52
  private int[] dijkstra(ArrayList<ArrayList<Integer>> adj) {
53

54
    int n = adj.size();
55

56
    int[] dist = new int[n];
57
    boolean[] visited = new boolean[n];
58

59
    Arrays.fill(dist, Integer.MAX_VALUE);
60
    dist[0] = 0;
61

62
    PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
63

64
    pq.add(new int[] {0, 0});
65

66
    while (!pq.isEmpty()) {
67
      int[] node = pq.remove();
68
      if (!visited[node[0]]) {
69
        visited[node[0]] = true;
70
        for (int nbr : adj.get(node[0])) {
71
          if (dist[nbr] > dist[node[0]] + 1) {
72
            dist[nbr] = dist[node[0]] + 1;
73
            pq.add(new int[] {nbr, dist[nbr]});
74
          }
75
        }
76
      }
77
    }
78

79
    return dist;
80
  }
81
}