3108. Minimum Cost Walk in Weighted Graph

[mah-shamim]

Topics: Array, Bit Manipulation, Union Find, 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] = [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 <= 105
• 0 <= edges.length <= 105
• edges[i].length == 3
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= wi <= 105
• 1 <= query.length <= 105
• query[i].length == 2
• 0 <= si, ti <= n - 1
• si != ti

Hint:

1. The intended solution uses Disjoint Set Union.
2. Notice that, if u and v are not connected then the answer is -1, otherwise we can use all the edges from the connected component where both belong to.

[mah-shamim]

We need to determine the minimum cost of a walk between two nodes in a weighted undirected graph, where the cost is defined as the bitwise AND of the weights of all edges traversed during the walk. If no such walk exists, the answer should be -1.

Approach

1. Disjoint Set Union (DSU): First, we use DSU to identify connected components in the graph. This helps us quickly determine if two nodes are reachable from each other.
2. Compute Component AND Values: For each connected component, compute the bitwise AND of all edge weights within that component. This value represents the minimum possible cost for any walk within the component.
3. Query Processing: For each query, check if the start and end nodes belong to the same connected component. If they do, return the precomputed AND value for that component; otherwise, return -1.

Let's implement this solution in PHP: 3108. Minimum Cost Walk in Weighted Graph

<?php
class DSU {
    /**
     * @var array
     */
    private $parent;
    /**
     * @var array
     */
    private $rank;

    /**
     * @param $n
     */
    public function __construct($n) {
        $this->parent = array();
        $this->rank = array();
        for ($i = 0; $i < $n; $i++) {
            $this->parent[$i] = $i;
            $this->rank[$i] = 0;
        }
    }

    /**
     * @param $x
     * @return mixed
     */
    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    /**
     * @param $x
     * @param $y
     * @return bool
     */
    public function union($x, $y) {
        $xr = $this->find($x);
        $yr = $this->find($y);
        if ($xr == $yr) {
            return false;
        }
        if ($this->rank[$xr] < $this->rank[$yr]) {
            $this->parent[$xr] = $yr;
        } else {
            $this->parent[$yr] = $xr;
            if ($this->rank[$xr] == $this->rank[$yr]) {
                $this->rank[$xr]++;
            }
        }
        return true;
    }
}

/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param Integer[][] $query
 * @return Integer[]
 */
function minimumCost($n, $edges, $query) {
    $dsu = new DSU($n);
    foreach ($edges as $edge) {
        $dsu->union($edge[0], $edge[1]);
    }

    $component_and = array_fill(0, $n, -1);
    foreach ($edges as $edge) {
        $u = $edge[0];
        $w = $edge[2];
        $root = $dsu->find($u);
        $component_and[$root] &= $w;
    }

    $answer = array();
    foreach ($query as $q) {
        $s = $q[0];
        $t = $q[1];
        if ($dsu->find($s) != $dsu->find($t)) {
            array_push($answer, -1);
        } else {
            $root = $dsu->find($s);
            array_push($answer, $component_and[$root]);
        }
    }

    return $answer;
}

// Example usage:
$n = 5;
$edges = [[0,1,7],[1,3,7],[1,2,1]];
$query = [[0,3],[3,4]];
print_r(minimumCost($n, $edges, $query));  // Output: [1,-1]

$n = 3;
$edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]];
$query = [[1,2]];
print_r(minimumCost($n, $edges, $query));  // Output: [0]
?>

Explanation:

1. DSU Initialization: We initialize the DSU structure to keep track of connected components. Each node starts as its own parent, and we use union by rank to optimize merging components.
2. Union Operations: For each edge, we unite the nodes it connects, effectively building the connected components.
3. Component AND Calculation: After forming the connected components, we compute the bitwise AND of all edge weights in each component. This is done by iterating over each edge and updating the AND value for the root of its connected component.
4. Query Handling: For each query, we check if the start and end nodes are in the same component using the DSU find operation. If they are, we return the precomputed AND value for that component; otherwise, we return -1.

This approach efficiently handles the problem constraints using union-find for connectivity and bitwise operations to determine the minimum path cost.

[kovatz]

Thanks for solving the problem of "Minimum Cost Walk in Weighted Graph"

[mah-shamim]

Thanks