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

minimumCost.js

/**
 * Finds the minimum cost to connect queried nodes in a weighted graph.
 * 
 * @param {number} n - The number of nodes in the graph.
 * @param {number[][]} edges - The edges of the graph, where each edge is represented as [u, v, w].
 * @param {number[][]} query - An array of queries, where each query is represented as [s, t].
 * @return {number[]} - An array where each element corresponds to the minimum cost of connecting the queried nodes.
 */
var minimumCost = function(n, edges, query) {
    // Initialize Union-Find (Disjoint Set Union) structures
    const parent = Array.from({ length: n }, (_, i) => i); // Tracks the parent of each node
    const rank = Array(n).fill(0); // Tracks the rank (tree height) for union optimization
    const cc = Array(n).fill(0x7FFFFFFF); // Store the minimum weight in each connected component

    // Helper function to find the root of a node with path compression
    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    };

    // Helper function to union two nodes
    const union = (x, y) => {
        const rootX = find(x);
        const rootY = find(y);

        // Union by rank to maintain a balanced tree
        if (rootX !== rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    };

    // Process all edges to union connected nodes
    for (const [u, v, w] of edges) {
        union(u, v);
    }

    // Calculate the minimum edge weight within each connected component
    for (const [u, v, w] of edges) {
        const root = find(u); // Find the root of the component
        cc[root] &= w; // Update the minimum weight using bitwise AND
    }

    // Resolve each query by checking if the nodes are in the same connected component
    const result = [];
    for (const [s, t] of query) {
        if (find(s) !== find(t)) {
            result.push(-1); // Nodes are not connected
        } else {
            result.push(cc[find(s)]); // Return the minimum edge weight for the connected component
        }
    }

    return result; // Return the results for all queries
};