'2025/03/20'에 해당되는 글 1건

Leetcode Problem:

• Minimum Cost Walk in Weighted Graph

Summary

• Find the minimum cost of a walk between two nodes in an undirected weighted graph.

Approach

• Disjoint Set Union (DSU) algorithm is used to find the minimum cost of a walk between two nodes in an undirected weighted graph
• The DSU algorithm is used to find the set that each node belongs to and the minimum cost of the walk is calculated by performing a bitwise AND operation on the weights of the edges in the same set.

Complexity

• O(n + m log n), where n is the number of nodes and m is the number of edges.

Explanation

• The solution code first initializes the DSU array and the groupWeight array
• Then it iterates over the edges and updates the groupWeight array by performing a bitwise AND operation on the weights of the edges in the same set
• Finally, it iterates over the queries and calculates the minimum cost of the walk for each query by performing a bitwise AND operation on the weights of the edges in the same set.

Solution Code:

class Solution {
public:
    int uf[100001];
    int groupWeight[100001];
    int disjointSet(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    vector minimumCost(int n, vector>& edges, vector>& query) {
        for(int i = 0 ; i < n ;i++){
            uf[i] = i;
            groupWeight[i] = 0x0FFFFFFF;
        }
        for(int i = 0; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            int w = edges[i][2];
            int ww = groupWeight[disjointSet(a)] & groupWeight[disjointSet(b)] & w;
            uf[disjointSet(a)] = disjointSet(b);
            groupWeight[disjointSet(a)] = ww;
        }
        vector ans;
        for(int i = 0 ; i < query.size(); i++){
            int s = query[i][0];
            int e = query[i][1];
            if(disjointSet(s) == disjointSet(e)){
                ans.push_back(groupWeight[disjointSet(s)]);
            }else{
                ans.push_back(-1);
            }
        }
        return ans;
    }
};