leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2045.cpp (1235B)

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 };