1
class Solution {
2
 public:
3
  int secondMinimum(int n, vector<vector<int>> &edges, int time, int change) {
4
    // if the shortest path from 1 to n is of length L
5
    // find whether there is a path of length L+1
6
    // there is always a path of length L+2
7

8
    vector<vector<int>> adj(n);
9
    for (auto &e : edges) {
10
      int u = e[0] - 1, v = e[1] - 1;
11
      adj[u].push_back(v);
12
      adj[v].push_back(u);
13
    }
14

15
    // bfs from goal
16
    vector<int> d(n, 1e9);
17
    d[n - 1] = 0;
18
    queue<int> q;
19
    q.push(n - 1);
20
    while (!q.empty()) {
21
      int cur = q.front();
22
      q.pop();
23
      for (auto nei : adj[cur]) {
24
        if (d[nei] == 1e9) {
25
          d[nei] = d[cur] + 1;
26
          q.push(nei);
27
        }
28
      }
29
    }
30

31
    // check the existence of a path with length = d[0]+1
32
    int len = d[0] + 2;
33
    q.push(0);
34
    bool done = false;
35
    while (!q.empty()) {
36
      int cur = q.front();
37
      q.pop();
38
      for (auto nei : adj[cur]) {
39
        if (d[nei] == d[cur]) {
40
          len--;
41
          done = true;
42
          break;
43
        } else if (d[nei] == d[cur] - 1) {
44
          q.push(nei);
45
        }
46
      }
47
      if (done) break;
48
    }
49

50
    // calculate the time needed
51
    // light : green in [0, c),  [2c, 3c), ...
52
    //          red  in [c, 2c), [3c, 4c), ...
53
    int currTime = 0;
54
    // cout << len << '\n';
55
    for (int i = 0; i < len; i++) {
56
      if ((currTime / change) % 2 == 1) // have to wait until the signal turns into green
57
        currTime = ((currTime / change) + 1) * change;
58
      currTime += time;
59
    }
60
    return currTime;
61
  }
62
};