Checking Existence of Edge Length Limited Paths

The most straightforward approach is to process each query independently. For every query, we can construct a new graph that only includes edges with weights strictly less than the query's limit. After building this subgraph, we can use a standard graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to determine if a path exists between the two specified nodes.

• Create a boolean array answer of size queries.length.
• For each query j from 0 to queries.length - 1:
  • Let p = queries[j][0], q = queries[j][1], limit = queries[j][2].
  • Build an adjacency list adj for a graph with n nodes.
  • For each edge (u, v, dist) in edgeList:
    • If dist < limit, add v to adj[u] and u to adj[v].
  • Use BFS or DFS to check if q is reachable from p in the graph represented by adj.
  • If reachable, set answer[j] = true, otherwise answer[j] = false.
• Return answer.

For each query (p, q, limit):

1. Initialize an empty adjacency list to represent the graph for this specific query.
2. Iterate through the entire edgeList. If an edge's weight is less than the given limit, add it to the adjacency list.
3. Once the graph is constructed, perform a BFS starting from node p.
4. Use a visited array to keep track of nodes already visited to avoid cycles and redundant work.
5. A queue is used for the BFS. Initially, it contains only the start node p.
6. In a loop, dequeue a node. If this node is the target node q, we have found a path, and the result for this query is true.
7. If the node is not the target, add all of its unvisited neighbors to the queue and mark them as visited.
8. If the queue becomes empty and q has not been reached, it means there is no path between p and q under the given limit. The result is false.
9. This process is repeated for all queries.

import java.util.*;

class Solution {
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        int qLen = queries.length;
        boolean[] answer = new boolean[qLen];

        for (int i = 0; i < qLen; i++) {
            int p = queries[i][0];
            int q = queries[i][1];
            int limit = queries[i][2];

            // Build graph for the current query
            List<List<Integer>> adj = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                adj.add(new ArrayList<>());
            }
            for (int[] edge : edgeList) {
                if (edge[2] < limit) {
                    adj.get(edge[0]).add(edge[1]);
                    adj.get(edge[1]).add(edge[0]);
                }
            }

            // Check connectivity using BFS
            answer[i] = bfs(p, q, n, adj);
        }
        return answer;
    }

    private boolean bfs(int start, int end, int n, List<List<Integer>> adj) {
        if (start == end) return true;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == end) {
                return true;
            }
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
}