Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost Walk in Weighted Graph

Minimum Cost Walk in Weighted Graph asks you to find, for each vertex query, the minimum bitwise AND of edge weights on any walk, including repeated edges, or minus one if no route exists.

Statement

There is an undirected weighted graph with n vertices labeled from 00 to n −1- 1. You are given an integer n and an array edges, where edges[i] = [u_i, v_i, w_i] indicates an undirected edge between vertices u_i and v_i with weight w_i.

You are also given an array query, where each query[i] = [s_i, t_i].

The cost of a walk is defined as the bitwise AND of the weights of all edges traversed along that path. A walk can visit vertices and edges multiple times.

For each query, find the minimum cost among all possible walks from vertex s_i to vertex t_i. If no walk exists between s_i and t_i, the answer is −1-1.

Return an array of integers representing the answer to each query.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 0≤0 \leq edges.length ≤105\leq 10^5

  • edges[i].length =3= 3

  • 0≤0 \leq u_i, v_i ≤\leq n −1- 1

  • u_i ≠\neq v_i

  • 0≤0 \leq w_i ≤105\leq 10^5

  • 1≤1 \leq query.length ≤105\leq 10^5

  • query[i].length =2= 2

  • 0≤0 \leq s_i, t_i ≤\leq n −1- 1

  • s_i ≠\neq t_i

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost Walk in Weighted Graph

Minimum Cost Walk in Weighted Graph asks you to find, for each vertex query, the minimum bitwise AND of edge weights on any walk, including repeated edges, or minus one if no route exists.

Statement

There is an undirected weighted graph with n vertices labeled from 00 to n −1- 1. You are given an integer n and an array edges, where edges[i] = [u_i, v_i, w_i] indicates an undirected edge between vertices u_i and v_i with weight w_i.

You are also given an array query, where each query[i] = [s_i, t_i].

The cost of a walk is defined as the bitwise AND of the weights of all edges traversed along that path. A walk can visit vertices and edges multiple times.

For each query, find the minimum cost among all possible walks from vertex s_i to vertex t_i. If no walk exists between s_i and t_i, the answer is −1-1.

Return an array of integers representing the answer to each query.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 0≤0 \leq edges.length ≤105\leq 10^5

  • edges[i].length =3= 3

  • 0≤0 \leq u_i, v_i ≤\leq n −1- 1

  • u_i ≠\neq v_i

  • 0≤0 \leq w_i ≤105\leq 10^5

  • 1≤1 \leq query.length ≤105\leq 10^5

  • query[i].length =2= 2

  • 0≤0 \leq s_i, t_i ≤\leq n −1- 1

  • s_i ≠\neq t_i