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 Description
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 roadExample 1:
Input: g_nodes = 5, g_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]
Output: ["YES", "YES", "NO", "NO", "YES", "YES", "YES"]
Explanation: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
An unknown urban legend 🥲
input:
output: