Problem · Graph
Checking Your Route 🚗
Learn this problemProblem statement
A ride hailing company sometimes travels between cities. To avoid delays, a driver first checks for the shortest routes. There is a map of the cities and their bidirectional roads represented by a graph of nodes and edges. Determine the paths from the first node to the last node and choose the shortest length. Now select all paths that are that length. These are the shortest paths. Return an array of strings, one for each road in order, where the value is YES if the road is along any shortest path or NO if it is not. The roads or edges are named using their 1-based index within the input arrays.
Function
checkRoute(g_nodes: int, g_from: int[], g_to: int[], g_weight: int[]) → String[]
Complete the function classifyEdges in the editor.
classifyEdges has the following parameter(s):
int g_nodes: an integer, the num of nodesint g_from[g_edges]: an array of integers, the start g_nodes for each roadint g_to[g_edges]: an array of integers, the end g_nodes for each roadint g_weight[g_edges]: an array of integers, the lengths of each roadExamples
Example 1
g_nodes = 5g_from = [1, 2, 3, 4, 5, 1, 5]g_to = [2, 3, 4, 5, 1, 3, 3]g_weight = [1, 1, 1, 1, 3, 2, 1]return = ["YES", "YES", "NO", "NO", "YES", "YES", "YES"]
Given a map of g_nodes = 5 nodes, the starting nodes, ending nodes and road lengths are:
The traveller must travel from city 1 to city g_nodes, so from node 1 to node S in thsi case
The shortest path is 3 units long and there are three paths of that length: 1->5, 1->2->3->5, and 1->3->5
Return an array of strings, one for each road in order, where the values is YES if a road is along a shortes path or NO if it is not. In this case the resulting array is ["YES", "YES", "NO", "NO", "YES", "YES", "YES"]. The third and fourth raods connect nodes (3, 4) and (4, 5) respectively. They are not on a shorest path, i.e. one with a len of 3 in this case
Constraints
An unknown urban legend 🥲