Package g1601_1700.s1697_checking_existence_of_edge_length_limited_paths

Class Solution

java.lang.Object

g1601_1700.s1697_checking_existence_of_edge_length_limited_paths.Solution

public class Solution
extends Object

1697 - Checking Existence of Edge Length Limited Paths.<p>Hard</p> <p>An undirected graph of <code>n</code> nodes is defined by <code>edgeList</code>, where <code>edgeList[i] = [u_i, v_i, dis_i]</code> denotes an edge between nodes <code>u_i</code> and <code>v_i</code> with distance <code>dis_i</code>. Note that there may be <strong>multiple</strong> edges between two nodes.</p> <p>Given an array <code>queries</code>, where <code>queries[j] = [p_j, q_j, limit_j]</code>, your task is to determine for each <code>queries[j]</code> whether there is a path between <code>p_j</code> and <code>q_j</code> such that each edge on the path has a distance <strong>strictly less than</strong> <code>limit_j</code> .</p> <p>Return <em>a <strong>boolean array</strong></em> <code>answer</code><em>, where</em> <code>answer.length == queries.length</code> <em>and the</em> <code>j^th</code> <em>value of</em> <code>answer</code> <em>is</em> <code>true</code> <em>if there is a path for</em> <code>queries[j]</code> <em>is</em> <code>true</code><em>, and</em> <code>false</code> <em>otherwise</em>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/12/08/h.png" alt="" /></p> <p><strong>Input:</strong> n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]</p> <p><strong>Output:</strong> [false,true]</p> <p><strong>Explanation:</strong> The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.</p> <p>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.</p> <p>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.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/12/08/q.png" alt="" /></p> <p><strong>Input:</strong> n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]</p> <p><strong>Output:</strong> [true,false] <strong>Exaplanation:</strong> The above figure shows the given graph.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>2 <= n <= 10⁵</code></li> <li><code>1 <= edgeList.length, queries.length <= 10⁵</code></li> <li><code>edgeList[i].length == 3</code></li> <li><code>queries[j].length == 3</code></li> <li><code>0 <= u_i, v_i, p_j, q_j <= n - 1</code></li> <li><code>u_i != v_i</code></li> <li><code>p_j != q_j</code></li> <li><code>1 <= dis_i, limit_j <= 10⁹</code></li> <li>There may be <strong>multiple</strong> edges between two nodes.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
boolean[]	distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

distanceLimitedPathsExist

public boolean[] distanceLimitedPathsExist(int n,
 int[][] edgeList,
 int[][] queries)