A map has n junctions, numbered 1 through n, joined by m two-way toll roads. Road i connects two distinct junctions and has a toll w_i. You are then given q queries. Each query gives a, b, and a limit, and asks: can you travel from junction a to junction b using only roads whose toll is strictly less than limit?
Answer each query with YES or NO, one per line, in the input order.
n and m.m lines: three integers u, v, w (junctions 1-indexed, u != v), a road and its toll.q, the number of queries.q lines: three integers a, b, limit.q lines, each YES or NO, answering the queries in order.
Example 1
Input
4 4 1 2 3 2 3 5 3 4 2 1 4 8 3 1 3 6 1 3 4 1 4 1
Expected
YES NO NO
Explanation
Query 1 (limit 6) may use roads 1-2(3), 2-3(5), 3-4(2); 1 reaches 3 via 1-2-3: YES. Query 2 (limit 4) may use only 1-2(3) and 3-4(2); 1 cannot reach 3: NO. Query 3 (limit 1) allows no roads: NO.
Example 2
Input
3 2 1 2 4 2 3 4 2 1 3 5 1 3 4
Expected
YES NO
Explanation
Query 1 (limit 5) uses both roads (toll 4 < 5): 1-2-3 reachable: YES. Query 2 (limit 4) allows no road (4 is not < 4): NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →