1697. Checking Existence of Edge Length Limited Paths

Hard

1.8K

43

An undirected graph of `n`

nodes is defined by `edgeList`

, where `edgeList[i] = [u`

denotes an edge between nodes _{i}, v_{i}, dis_{i}]`u`

and _{i}`v`

with distance _{i}`dis`

. Note that there may be _{i}**multiple** edges between two nodes.

Given an array `queries`

, where `queries[j] = [p`

, your task is to determine for each _{j}, q_{j}, limit_{j}]`queries[j]`

whether there is a path between `p`

and _{j}`q`

_{j}_{ }such that each edge on the path has a distance **strictly less than** `limit`

._{j}

Return *a boolean array *

`answer`

`answer.length == queries.length`

`j`^{th}

`answer`

`true`

`queries[j]`

`true`

`false`

**Example 1:**

Input:n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]Output:[false,true]Explanation:The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16. For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query. For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

**Example 2:**

Input:n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]Output:[true,false]Explanation:The above figure shows the given graph.

**Constraints:**

`2 <= n <= 10`

^{5}`1 <= edgeList.length, queries.length <= 10`

^{5}`edgeList[i].length == 3`

`queries[j].length == 3`

`0 <= u`

_{i}, v_{i}, p_{j}, q_{j}<= n - 1`u`

_{i}!= v_{i}`p`

_{j}!= q_{j}`1 <= dis`

_{i}, limit_{j}<= 10^{9}- There may be
**multiple**edges between two nodes.

Accepted

45.8K

Submissions

72.6K

Acceptance Rate

63.0%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved