1
class Solution {
2
  public int secondMinimum(int n, int[][] edges, int time, int change) {
3
    Map<Integer, List<Integer>> g = new HashMap();
4
    for (int[] e : edges) {
5
      int u = e[0], v = e[1];
6
      g.computeIfAbsent(u, x -> new ArrayList()).add(v);
7
      g.computeIfAbsent(v, x -> new ArrayList()).add(u);
8
    }
9
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
10
    q.offer(new int[] {1, 0});
11
    int[] uniqueVisit = new int[n + 1]; // uniqueVisit limit to 2 <==> relax twice at most
12
    int[] dis = new int[n + 1];
13
    Arrays.fill(dis, -1);
14
    while (!q.isEmpty()) {
15
      int size = q.size();
16
      int[] cur = q.poll();
17
      int node = cur[0], t = cur[1]; // arriving time
18
      if (dis[node] == t || uniqueVisit[node] >= 2)
19
        continue; // skip if it's same value or has been relaxed twice already
20
      uniqueVisit[node]++;
21
      dis[node] = t;
22
      if (node == n && uniqueVisit[node] == 2) return dis[node];
23
      // generate leaving time (waiting the green light)
24
      if ((t / change) % 2 != 0) t = (t / change + 1) * change;
25
      for (int nei : g.getOrDefault(node, new ArrayList<>())) {
26
        q.offer(new int[] {nei, t + time});
27
      }
28
    }
29
    return -1;
30
  }
31
}