3348. Minimum Cost Walk In Weighted Graph¶
Difficulty: Hard
LeetCode Problem View on GitHub
3348. Minimum Cost Walk in Weighted Graph
Hard
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] = [ui, vi, wi] indicates that there is an edge between vertices ui and vi with a weight of wi.
A walk on a 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.
The cost of a walk starting at node u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w0, w1, w2, ..., wk, then the cost is calculated as w0 & w1 & w2 & ... & wk, where & denotes the bitwise AND operator.
You are also given a 2D array query, where query[i] = [si, ti]. For each query, you need to find the minimum cost of the walk starting at vertex si and ending at vertex ti. If there exists no such walk, the answer is -1.
Return the array answer, where answer[i] denotes the minimum cost of a walk for query i.
Example 1:
Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
Output: [1,-1]
Explanation:
To achieve the cost of 1 in the first query, we need to move on the following edges: 0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7).
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
Example 2:
Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
Output: [0]
Explanation:
To achieve the cost of 0 in the first query, we need to move on the following edges: 1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).
Constraints:
2 <= n <= 1050 <= edges.length <= 105edges[i].length == 30 <= ui, vi <= n - 1ui != vi0 <= wi <= 1051 <= query.length <= 105query[i].length == 20 <= si, ti <= n - 1si != ti
Solution¶
class Solution {
private ArrayList<ArrayList<Pair>> adj;
private HashMap<Integer, Integer> map;
private ArrayList<Integer> nodes;
private int vis[];
static class Pair {
int node;
int distance;
public Pair(int node, int distance) {
this.node = node;
this.distance = distance;
}
@Override
public String toString() {
return "(" + node + " " + distance + ")";
}
}
static class custom_sort implements Comparator<Pair> {
@Override
public int compare(Pair first, Pair second) {
return Integer.compare(first.distance, second.distance);
}
}
static class DSU {
private int parent[];
private int size[];
public DSU(int n) {
parent = new int[n + 1];
size = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void merge(int u , int v) {
u = Leader(u);
v = Leader(v);
if (size[v] > size[u]) {
int temp = u;
u = v;
v = temp;
}
parent[v] = u;
size[u] += size[v];
}
public int Leader(int u) {
if (parent[u] == u) return parent[u] = u;
return parent[u] = Leader(parent[u]);
}
}
public int[] minimumCost(int n, int[][] edges, int[][] query) {
map = new HashMap<>();
nodes = new ArrayList<>();
DSU dsu = new DSU(n + 1);
adj = new ArrayList<>();
for (int i = 0; i <= n + 1; i++) adj.add(new ArrayList<>());
for (int current[] : edges) {
int u = current[0];
int v = current[1];
int wt = current[2];
if (dsu.Leader(u) != dsu.Leader(v)) dsu.merge(u , v);
adj.get(u).add(new Pair(v, wt));
adj.get(v).add(new Pair(u, wt));
}
vis = new int[n + 1];
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
nodes.clear();
dfs(i, -1);
ArrayList<Integer> temp = new ArrayList<>();
for (int j = 0; j < nodes.size(); j++) {
int u = nodes.get(j);
for (int k = 0; k < adj.get(u).size(); k++) temp.add(adj.get(u).get(k).distance);
}
if (temp.size() == 0) continue;
int and = temp.get(0);
for (int ele : temp) and &= ele;
if (and != -1) {
for (int ele : nodes) map.put(ele, and);
}
}
}
int res[] = new int[query.length];
int k = 0;
for (int current[] : query) {
int src = current[0];
int dst = current[1];
if (dsu.Leader(src) != dsu.Leader(dst)) {
res[k++] = -1;
continue;
}
res[k++] = map.get(src);
}
return res;
}
private void dfs(int u , int par) {
vis[u] = 1;
nodes.add(u);
for (int i = 0; i < adj.get(u).size(); i++) {
int child = adj.get(u).get(i).node;
if (vis[child] == 0) dfs(child , u);
}
}
private int min_dist(int n , int src, int dst) {
int dist[] = new int[n + 1];
Arrays.fill(dist, (int)(1e9));
PriorityQueue<Pair> pq = new PriorityQueue<>(new custom_sort());
for (int i = 0; i < adj.get(src).size(); i++) {
int child_node = adj.get(src).get(i).node;
int child_dist = adj.get(src).get(i).distance;
dist[child_node] = child_dist;
pq.offer(new Pair(child_node, dist[child_node]));
}
while (pq.size() > 0) {
int current_node = pq.peek().node;
int current_dist = pq.peek().distance;
pq.poll();
for (int i = 0; i < adj.get(current_node).size(); i++) {
int child_node = adj.get(current_node).get(i).node;
int child_dist = adj.get(current_node).get(i).distance;
if (dist[child_node] > (current_dist & child_dist)) {
dist[child_node] = current_dist & child_dist;
pq.offer(new Pair(child_node, dist[child_node]));
}
}
}
if(dist[dst] == (int)(1e9)) return -1;
return dist[dst];
}
}
Complexity Analysis¶
- Time Complexity:
O(?) - Space Complexity:
O(?)
Approach¶
Detailed explanation of the approach will be added here