Problem Brief

Checking Your Route 🚗

INTERNOA

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 nodes

int g_from[g_edges]: an array of integers, the start g_nodes for each road

int g_to[g_edges]: an array of integers, the end g_nodes for each road

int g_weight[g_edges]: an array of integers, the lengths of each road

1Example 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

Constraints

Limits and guarantees your solution can rely on.

An unknown urban legend 🥲