1697. Checking Existence of Edge Length Limited Paths Hard

1/**
2 * [1697] Checking Existence of Edge Length Limited Paths
3 *
4 * An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.
5 * Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .
6 * Return a boolean array answer, where answer.length == queries.length and the j^th value of answer is true if there is a path for queries[j] is true, and false otherwise.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/h.png" style="width: 267px; height: 262px;" />
10 * Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
11 * Output: [false,true]
12 * Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
13 * 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.
14 * 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.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/q.png" style="width: 390px; height: 358px;" />
18 * Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
19 * Output: [true,false]
20 * Exaplanation: The above figure shows the given graph.
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	2 <= n <= 10^5
26 * 	1 <= edgeList.length, queries.length <= 10^5
27 * 	edgeList[i].length == 3
28 * 	queries[j].length == 3
29 * 	0 <= ui, vi, pj, qj <= n - 1
30 * 	ui != vi
31 * 	pj != qj
32 * 	1 <= disi, limitj <= 10^9
33 * 	There may be multiple edges between two nodes.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/
39// discuss: https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn distance_limited_paths_exist(n: i32, edge_list: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<bool> {
45        
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_1697() {
57    }
58}
59