Prerequisite-Aware Delivery Route
Flipkart's logistics network is vast and complex, often involving critical delivery hubs that handle specialized items or require specific routing procedures. Optimizing routes to minimize delivery time is crucial for efficiency and customer satisfaction. This problem challenges you to find the shortest possible route through a delivery network, ensuring all designated critical hubs are visited while respecting specific visit order prerequisites.
Implement the function findMinPrerequisiteAwareRoute that calculates the minimum total distance to travel from a startNode to an endNode in a given directed, weighted graph. The path must satisfy the following conditions:
criticalHubs must be visited at least once along the route.prerequisite pair [idxA, idxB], criticalHubs[idxA] must be visited before criticalHubs[idxB] on the path.Your solution should return the minimum total distance. If no such valid path exists, return -1.
Function Signature:
function findMinPrerequisiteAwareRoute(n: number, edges: number[][], startNode: number, endNode: number, criticalHubs: number[], prerequisites: number[][]): number
Parameters:
n: An integer representing the number of nodes in the graph, labeled from 0 to n-1.edges: An array of arrays, where each inner array [u, v, weight] represents a directed edge from node u to node v with a non-negative weight (distance).startNode: The starting node for the route.endNode: The final destination node for the route.criticalHubs: An array of unique node IDs that must be visited. These nodes are part of the graph (0 to n-1). The order of nodes in this array defines their indices for prerequisites (e.g., criticalHubs[0] is the first critical hub).prerequisites: An array of arrays, where each inner array [idxA, idxB] means that criticalHubs[idxA] must be visited before criticalHubs[idxB]. idxA and idxB are valid indices into the criticalHubs array.Return Value:
-1 if no such route exists.criticalHubs: If criticalHubs is empty, the task simplifies to finding the shortest path from startNode to endNode without any additional requirements.startNode or endNode as criticalHubs: If startNode or endNode are among the criticalHubs, they are considered 'visited' at the very beginning or end of the path respectively, and their prerequisite constraints must still be met.prerequisites do not form a cycle (e.g., A before B, B before C, C before A).u == v for an edge [u, v, weight]).Examples
Example 1
Input:
n = 3, edges = [[0,1,10],[1,2,10],[0,2,25]], startNode = 0, endNode = 2, criticalHubs = [1], prerequisites = []
Output:
20
Note:
The shortest path from 0 to 2 that visits node 1 is 0 -> 1 (cost 10) -> 2 (cost 10), total 20. The direct path 0 -> 2 (cost 25) is longer.
Example 2
Input:
n = 4, edges = [[0,1,10],[1,2,10],[2,3,10],[0,3,100],[0,2,25],[1,3,20]], startNode = 0, endNode = 3, criticalHubs = [1, 2], prerequisites = [[0, 1]]
Output:
30
Note:
Critical hubs: criticalHubs[0] = node 1, criticalHubs[1] = node 2. Prerequisite: node 1 must be visited before node 2. Path 0 -> 1 (cost 10, visits criticalHubs[0]). Current mask indicates criticalHubs[0] visited. Then 1 -> 2 (cost 10, visits criticalHubs[1]). Prerequisite for criticalHubs[1] (criticalHubs[0]) is met. Current mask indicates both visited. Then 2 -> 3 (cost 10). Total cost: 10 + 10 + 10 = 30. Attempting 0 -> 2 (cost 25) directly would visit criticalHubs[1] before criticalHubs[0], violating the prerequisite, hence this path is invalid.
Example 3
Input:
n = 3, edges = [[0,1,10],[1,2,10]], startNode = 0, endNode = 2, criticalHubs = [0, 1], prerequisites = [[1, 0]]
Output:
-1
Note:
Critical hubs: criticalHubs[0] = node 0, criticalHubs[1] = node 1. Prerequisite: node 1 must be visited before node 0. Starting at node 0 means criticalHubs[0] is considered visited. However, the prerequisite states that criticalHubs[1] must be visited before criticalHubs[0]. This creates an immediate violation at the start, as criticalHubs[0] is 'visited' first by being the start node, but its prerequisite (criticalHubs[1]) has not been met yet. Thus, no valid path exists.
Constraints
1 <= n <= 500 <= edges.length <= n * (n - 1)0 <= u, v < n for all edges1 <= weight <= 1000 for all edges0 <= startNode, endNode < n0 <= criticalHubs.length <= 10 (This constraint is crucial for performance)criticalHubs are unique and within 0 to n-1.0 <= prerequisites.length <= criticalHubs.length * (criticalHubs.length - 1) / 20 <= idxA, idxB < criticalHubs.length for all prerequisites.idxA != idxB for all prerequisites.Loading editor...