aboutsummaryrefslogtreecommitdiff
path: root/other
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-30 21:18:48 -0600
committerJack Sangdahl <[email protected]>2025-03-30 21:18:48 -0600
commite1b13ac0df29496c79403cbe20c64a3c7eb414b7 (patch)
tree11f6cd9354b3d30b3d454f1dbf6b8aa26989aaaf /other
parent62ec80fb2041268d4d7aaad4cbe5b3fc7c67ce3f (diff)
downloadleetcode-e1b13ac0df29496c79403cbe20c64a3c7eb414b7.tar.gz
leetcode-e1b13ac0df29496c79403cbe20c64a3c7eb414b7.zip
chore: move remaining cpp files to other/
Diffstat (limited to 'other')
-rw-r--r--other/min_cost_walk_weight_graph.cpp72
-rw-r--r--other/num_ways_arrive_dest.cpp62
2 files changed, 134 insertions, 0 deletions
diff --git a/other/min_cost_walk_weight_graph.cpp b/other/min_cost_walk_weight_graph.cpp
new file mode 100644
index 0000000..79f3a8b
--- /dev/null
+++ b/other/min_cost_walk_weight_graph.cpp
@@ -0,0 +1,72 @@
+// 3108. Minimum Cost Walk in Weighted Graph
+#include "leetcode.h"
+
+/*
+ * there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n
+ * - 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] =
+ * [u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and
+ * 'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices
+ * and edges. the walk starts and ends with a vertex, and each edge connects the
+ * vertex that comes before it and the vertex that comes after it. it's
+ * important to note that a walk may visit the same edge or vertex more than
+ * once. return the array 'answer' where 'answer[i]' denotes the minimum cost of
+ * a walk for query 'i'.
+ */
+
+class Solution {
+public:
+ vector<int> minimumCost(int n, vector<vector<int>> &edges,
+ vector<vector<int>> &query) {
+ vector<vector<int>> adj(n);
+ vector<int> cnt(n, (1 << 30) - 1);
+ for (vector<int> e : edges) {
+ int u = e[0], v = e[1], k = e[2];
+ adj[u].push_back(v);
+ adj[v].push_back(u);
+ cnt[u] &= k;
+ cnt[v] &= k;
+ }
+ queue<int> q;
+ vector<int> group(n, -1);
+ for (int i = 0; i < n; i++) {
+ if (group[i] == -1) {
+ group[i] = i;
+ q.push(i);
+ while (!q.empty()) {
+ int u = q.front();
+ q.pop();
+ cnt[i] &= cnt[u];
+ for (int v : adj[u]) {
+ if (group[v] == -1) {
+ group[v] = i;
+ q.push(v);
+ }
+ }
+ }
+ }
+ }
+ vector<int> ans;
+ for (vector<int> qs : query) {
+ int s = qs[0], t = qs[1];
+ if (s == t)
+ ans.push_back(0);
+ else
+ ans.push_back(group[s] == group[t] ? cnt[group[s]] : -1);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1, 7}, {1, 3, 7}, {1, 2, 1}}, q1 = {{0, 3}, {3, 4}};
+ vvd e2 = {{0, 2, 7}, {0, 1, 15}, {1, 2, 6}, {1, 2, 1}}, q2 = {{1, 2}};
+ vector<int> mc1 = obj.minimumCost(5, e1, q1);
+ vector<int> mc2 = obj.minimumCost(3, e2, q2);
+ for (auto i : mc1)
+ printf("%d ", i); // expect: 1 -1
+ printf("\n");
+ for (auto i : mc2)
+ printf("%d ", i); // expect: 0
+ printf("\n");
+}
diff --git a/other/num_ways_arrive_dest.cpp b/other/num_ways_arrive_dest.cpp
new file mode 100644
index 0000000..416d811
--- /dev/null
+++ b/other/num_ways_arrive_dest.cpp
@@ -0,0 +1,62 @@
+// 1976. Number of Ways to Arrive at Destination
+#include "leetcode.h"
+
+/*
+ * you are in a city that consists of 'n' intersections numbered from 0 to 'n -
+ * 1' with bi directional roads between some intersections. the inputs are
+ * generated such that you can reach any intersection from any other
+ * intersection and that there is at most one road between any two
+ * intersections. you are given an integer 'n' and a 2d integer array 'roads'
+ * where 'roads[i] = [u_i, v_i, t_i]' means that there is a road between
+ * intersections 'u' and 'v' that takes 't' minutes to travel. you want to know
+ * in how many ways you can travel from interseciton 0 to intersection 'n - 1'.
+ */
+
+class Solution {
+public:
+ int countPaths(int n, vector<vector<int>> &roads) {
+ vector<vector<pair<long long, long long>>> graph(n);
+ for (auto &r : roads) {
+ long long u = r[0], v = r[1], t = r[2];
+ graph[u].push_back({v, t});
+ graph[v].push_back({u, t});
+ }
+ return dijkstra(graph, n, 0);
+ }
+
+private:
+ int mod = 1e9 + 7;
+ int dijkstra(const vector<vector<pair<long long, long long>>> &graph, int n,
+ int src) {
+ vector<long long> dist(n, LONG_MAX), ways(n);
+ ways[src] = 1;
+ dist[src] = 0;
+ priority_queue<pair<long long, long long>,
+ vector<pair<long long, long long>>, greater<>>
+ pq;
+ pq.push({0, 0});
+ while (!pq.empty()) {
+ auto [d, u] = pq.top();
+ pq.pop();
+ if (d > dist[u])
+ continue;
+ for (auto [v, t] : graph[u]) {
+ if (dist[v] > d + t) {
+ dist[v] = d + t;
+ ways[v] = ways[u];
+ } else if (dist[v] == d + t)
+ ways[v] = (ways[v] + ways[u]) % mod;
+ }
+ }
+ return ways[n - 1];
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd r1 = {{0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
+ {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}};
+ vvd r2 = {{1, 0, 10}};
+ printf("%d\n", obj.countPaths(7, r1)); // expect: 4
+ printf("%d\n", obj.countPaths(2, r2)); // expect: 1
+}