leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2045.cpp (1235B)

      1 class Solution {
      2     static int getTime(int steps, int time, int change) {
      3         int res = 0;
      4 
      5         while (--steps) {
      6             res += time;
      7             if ((res / change) % 2 == 0) continue;
      8             res = (res / change + 1) * change;
      9         }
     10 
     11         return res + time;
     12     }
     13 
     14   public:
     15     int secondMinimum(int n, const vector<vector<int>> &edges, int time, int change) const {
     16         vector<vector<int>> adj(n + 1);
     17         vector<int> steps(n + 1, 100001);
     18 
     19         for (const auto &edge : edges) {
     20             adj[edge[0]].push_back(edge[1]);
     21             adj[edge[1]].push_back(edge[0]);
     22         }
     23 
     24         queue<int> q;
     25         q.push(1);
     26 
     27         for (int step = 0; !q.empty() && step <= steps[n] + 1; step++) {
     28             for (int k = q.size(); k > 0; k--) {
     29                 const int root = q.front();
     30                 q.pop();
     31 
     32                 if (step == steps[root] || step > steps[root] + 1) continue;
     33                 steps[root] = min(steps[root], step);
     34 
     35                 if (root == n && step > steps[n]) return getTime(step, time, change);
     36                 for (const auto n : adj[root])
     37                     q.push(n);
     38             }
     39         }
     40 
     41         return getTime(steps[n] + 2, time, change);
     42     }
     43 };