aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_cost_walk_weight_graph.cpp72
-rw-r--r--min_cost_walk_weight_graph.py72
2 files changed, 144 insertions, 0 deletions
diff --git a/min_cost_walk_weight_graph.cpp b/min_cost_walk_weight_graph.cpp
new file mode 100644
index 0000000..79f3a8b
--- /dev/null
+++ b/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/min_cost_walk_weight_graph.py b/min_cost_walk_weight_graph.py
new file mode 100644
index 0000000..b1d2415
--- /dev/null
+++ b/min_cost_walk_weight_graph.py
@@ -0,0 +1,72 @@
+# 3108. Minimum Cost Walk in Weighted Graph
+
+"""
+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 UnionFind:
+ def __init__(self, size):
+ self.parent = [i for i in range(size)]
+ self.rank = [0 for _ in range(size)]
+ self.d = [~0 for _ in range(size)]
+
+ def find(self, node):
+ if self.parent[node] != node:
+ self.parent[node] = self.find(self.parent[node])
+ return self.parent[node]
+
+ def union(self, a, b, val):
+ p1, p2 = self.find(a), self.find(b)
+ if self.rank[p1] > self.rank[p2]:
+ self.parent[p2] = p1
+ self.d[p1] &= self.d[p2] & val
+ elif self.rank[p1] < self.rank[p2]:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ else:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ self.rank[p2] += 1
+
+
+class Solution(object):
+ def minimumCost(self, n, edges, query):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type query: List[List[int]]
+ :rtype: List[int]
+ """
+ uf = UnionFind(n)
+ for u, v, w in edges:
+ uf.union(u, v, w)
+ ans = []
+ for u, v in query:
+ if uf.find(u) != uf.find(v):
+ ans.append(-1)
+ else:
+ ans.append(uf.d[uf.find(u)])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.minimumCost(
+ n=5, edges=[[0, 1, 7], [1, 3, 7], [1, 2, 1]], query=[[0, 3], [3, 4]]
+ )
+ )
+ print(
+ obj.minimumCost(
+ n=3, edges=[[0, 2, 7], [0, 1, 15], [1, 2, 6], [1, 2, 1]], query=[[1, 2]]
+ )
+ )