3108.js

/** ------------------------------------------------------------------------------
 * 
 * 3108. Minimum Cost Walk in Weighted Graph
 * Topics: Graph, Union-Find
 * https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/?envType=daily-question&envId=2025-03-20
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[][]} query
 * @return {number[]}
 */
var minimumCost = function (n, edges, query) {
  let parent = []
  const merge = (v) => {
    if (parent[v] !== v) parent[v] = merge(parent[v])
    return parent[v]
  }
  const costs = []
  for (let i = 0; i < n; i++) {
    parent[i] = i
    costs[i] = 131071
  }

  for (const [u, v, w] of edges) {
    const p1 = merge(u)
    const p2 = merge(v)
    parent[p1] = p2
    costs[p1] = costs[p2] = costs[p1] & costs[p2] & w
  }

  for (let i = 0; i < n; i++) {
    parent[i] = merge(i)
  }

  const result = []
  for (const [s, t] of query) {
    if (s === t) result.push(0)
    else if (parent[s] === parent[t]) {
      result.push(costs[parent[s]])
    } else result.push(-1)
  }
  return result
}

console.log(
  minimumCost(
    5,
    [
      [0, 1, 7],
      [1, 3, 7],
      [1, 2, 1],
    ],
    [
      [0, 3],
      [3, 4],
    ],
  ),
)