leetcode

commit 66342962641aefca68f3742472458b027dda4f5a
parent f17ee1474ae2b77c40b99339e92643326928ef19
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 28 Jul 2024 14:11:08 +0200

Daily Problem

Diffstat:
A
Problems/2045.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/2045.cpp b/Problems/2045.cpp
@@ -0,0 +1,43 @@
+class Solution {
+    static int getTime(int steps, int time, int change) {
+        int res = 0;
+
+        while (--steps) {
+            res += time;
+            if ((res / change) % 2 == 0) continue;
+            res = (res / change + 1) * change;
+        }
+
+        return res + time;
+    }
+
+  public:
+    int secondMinimum(int n, const vector<vector<int>> &edges, int time, int change) const {
+        vector<vector<int>> adj(n + 1);
+        vector<int> steps(n + 1, 100001);
+
+        for (const auto &edge : edges) {
+            adj[edge[0]].push_back(edge[1]);
+            adj[edge[1]].push_back(edge[0]);
+        }
+
+        queue<int> q;
+        q.push(1);
+
+        for (int step = 0; !q.empty() && step <= steps[n] + 1; step++) {
+            for (int k = q.size(); k > 0; k--) {
+                const int root = q.front();
+                q.pop();
+
+                if (step == steps[root] || step > steps[root] + 1) continue;
+                steps[root] = min(steps[root], step);
+
+                if (root == n && step > steps[n]) return getTime(step, time, change);
+                for (const auto n : adj[root])
+                    q.push(n);
+            }
+        }
+
+        return getTime(steps[n] + 2, time, change);
+    }
+};
diff --git a/README.md b/README.md
@@ -1052,6 +1052,7 @@ for solving problems.
 |  2039  |   Medium   | [The Time When the Network Becomes Idle](Problems/2039.cpp)                                        |
 |  2043  |   Medium   | [Simple Bank System](Problems/2043.cpp)                                                            |
 |  2044  |   Medium   | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp)                                    |
+|  2045  |    Hard    | [Second Minimum Time to Reach Destination](Problems/2045.cpp)                                      |
 |  2049  |   Medium   | [Count Nodes With the Highest Score](Problems/2049.cpp)                                            |
 |  2050  |    Hard    | [Parallel Courses III](Problems/2050.cpp)                                                          |
 |  2058  |   Medium   | [Find the Minimum and Maximum Number of Nodes Between Critical Points](Problems/2058.cpp)          |