Company: Deshaw
Difficulty: medium
Valid Paths in Weighted Graph Given a weighted graph with route_nodes nodes and m bidirectional edges given in the array route_from and route_to and each edge having weight route_weight corresponding to it. A path between two nodes is considered valid if the weights of all the edges used in that path are the same. Given q queries, the i th query contains query_from[i] and query_to[i] , the starting and ending node of the paths, 0 ≤ i Example Given: n = 3 nodes, and m = 5 paths, route_from = [1, 1, 1, 2, 2] , route_to = [3, 2, 2, 3, 3] having route_weight = [3, 1, 2, 1, 3] . As shown in the diagram below: [Graph visualization showing nodes 1, 2, and 3 with weighted edges] There are q = 3 queries, query_from = [1, 1, 2] and query_to = [2, 3, 3] Between 1 and 2 there are 3 valid paths - 1 to 3 to 2 with weight of the edges as 3, 1 to 2 directly with weights of the edges as 1 and 2 respectively Between 1 and 3 there are 2 valid paths - 1 to 3 directly with the edge of weight 3 and 1 to 2 t