leetcode

commit 93006a9396d50b98bb40a900b0278244d74cb45b
parent 7e8b4b8f305eabbb95362c1b77d678f37dec7d90
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 11 Nov 2023 22:58:03 +0000

Daily Problem

Diffstat:
A
Problems/2642.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/Problems/2642.cpp b/Problems/2642.cpp
@@ -0,0 +1,34 @@
+class Graph {
+    typedef tuple<int, int> Edge;
+    vector<vector<Edge>> adj;
+
+  public:
+    Graph(int n, const vector<vector<int>> &edges) : adj(n) {
+        for (const auto &edge : edges)
+            addEdge(edge);
+    }
+
+    void addEdge(const vector<int> edge) { adj[edge[0]].push_back({edge[2], edge[1]}); }
+
+    int shortestPath(int node1, int node2) const {
+        if (node1 == node2) return 0;
+        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
+        static int seen[101];
+        memset(seen, 0x00, sizeof(seen));
+        for (const Edge edge : adj[node1])
+            pq.push(edge);
+        while (!pq.empty()) {
+            while (!pq.empty() && seen[get<1>(pq.top())])
+                pq.pop();
+            if (pq.empty()) break;
+            const auto [w, n] = pq.top();
+            pq.pop();
+            if (n == node2) return w;
+            seen[n] = true;
+            for (const auto [w2, n2] : adj[n]) {
+                if (!seen[n2]) pq.push({w + w2, n2});
+            }
+        }
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -884,6 +884,7 @@ for solving problems.
 |  2637  |    Easy    | [Promise Time Limit](Problems/2637.js)                                                             |
 |  2640  |   Medium   | [Find the Score of All Prefixes of an Array](Problems/2640.cpp)                                    |
 |  2641  |   Medium   | [Cousins in Binary Tree II](Problems/2641.cpp)                                                     |
+|  2642  |    Hard    | [Design Graph With Shortest Path Calculator](Problems/2642.cpp)                                    |
 |  2657  |   Medium   | [Find the Prefix Common Array of Two Arrays](Problems/2657.cpp)                                    |
 |  2665  |    Easy    | [Counter II](Problems/2665.js)                                                                     |
 |  2666  |    Easy    | [Allow One Function Call](Problems/2666.js)                                                        |