leetcode

0 class Solution {

1 static int getTime(int steps, int time, int change) {

2 int res = 0;

3

4 while (--steps) {

5 res += time;

6 if ((res / change) % 2 == 0) continue;

7 res = (res / change + 1) * change;

8 }

9

10 return res + time;

11 }

12

13 public:

14 int secondMinimum(int n, const vector<vector<int>> &edges, int time, int change) const {

15 vector<vector<int>> adj(n + 1);

16 vector<int> steps(n + 1, 100001);

17

18 for (const auto &edge : edges) {

19 adj[edge[0]].push_back(edge[1]);

20 adj[edge[1]].push_back(edge[0]);

21 }

22

23 queue<int> q;

24 q.push(1);

25

26 for (int step = 0; !q.empty() && step <= steps[n] + 1; step++) {

27 for (int k = q.size(); k > 0; k--) {

28 const int root = q.front();

29 q.pop();

30

31 if (step == steps[root] || step > steps[root] + 1) continue;

32 steps[root] = min(steps[root], step);

33

34 if (root == n && step > steps[n]) return getTime(step, time, change);

35 for (const auto n : adj[root])

36 q.push(n);

37 }

38 }

39

40 return getTime(steps[n] + 2, time, change);

41 }

42 };