From e1b13ac0df29496c79403cbe20c64a3c7eb414b7 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sun, 30 Mar 2025 21:18:48 -0600 Subject: chore: move remaining cpp files to other/ --- min_cost_walk_weight_graph.cpp | 72 ------------------------------------ num_ways_arrive_dest.cpp | 62 ------------------------------- other/min_cost_walk_weight_graph.cpp | 72 ++++++++++++++++++++++++++++++++++++ other/num_ways_arrive_dest.cpp | 62 +++++++++++++++++++++++++++++++ 4 files changed, 134 insertions(+), 134 deletions(-) delete mode 100644 min_cost_walk_weight_graph.cpp delete mode 100644 num_ways_arrive_dest.cpp create mode 100644 other/min_cost_walk_weight_graph.cpp create mode 100644 other/num_ways_arrive_dest.cpp diff --git a/min_cost_walk_weight_graph.cpp b/min_cost_walk_weight_graph.cpp deleted file mode 100644 index 79f3a8b..0000000 --- a/min_cost_walk_weight_graph.cpp +++ /dev/null @@ -1,72 +0,0 @@ -// 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 minimumCost(int n, vector> &edges, - vector> &query) { - vector> adj(n); - vector cnt(n, (1 << 30) - 1); - for (vector 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 q; - vector 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 ans; - for (vector 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 mc1 = obj.minimumCost(5, e1, q1); - vector 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/num_ways_arrive_dest.cpp b/num_ways_arrive_dest.cpp deleted file mode 100644 index 416d811..0000000 --- a/num_ways_arrive_dest.cpp +++ /dev/null @@ -1,62 +0,0 @@ -// 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> &roads) { - vector>> 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>> &graph, int n, - int src) { - vector dist(n, LONG_MAX), ways(n); - ways[src] = 1; - dist[src] = 0; - priority_queue, - vector>, 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 -} 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 minimumCost(int n, vector> &edges, + vector> &query) { + vector> adj(n); + vector cnt(n, (1 << 30) - 1); + for (vector 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 q; + vector 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 ans; + for (vector 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 mc1 = obj.minimumCost(5, e1, q1); + vector 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> &roads) { + vector>> 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>> &graph, int n, + int src) { + vector dist(n, LONG_MAX), ways(n); + ways[src] = 1; + dist[src] = 0; + priority_queue, + vector>, 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 +} -- cgit v1.2.3