Shortest Route to Charging Station
Ola's electric vehicle (EV) fleet relies on efficient navigation to charging stations. Drivers often need to find the quickest route to recharge, especially when battery levels are low. This problem simulates a core part of our navigation system, focusing on finding the shortest path to any available charging station in a city, while accounting for temporary road closures.
Implement a function findShortestChargingRoute that determines the minimum number of road segments a driver needs to traverse to reach any charging station from a given starting point. You must avoid any roads that are currently marked as blocked due to maintenance or events.
Your function will receive the following parameters:
n: An integer representing the total number of intersections (nodes) in the city, indexed from 0 to n-1.roads: An array of [u, v] pairs, where each pair denotes a bidirectional road connecting intersection u and intersection v.startNode: An integer representing the driver's current intersection.chargingStations: An array of integers, where each integer is the index of an intersection that hosts a charging station.blockedRoads: An array of [u, v] pairs, where each pair denotes a bidirectional road that is currently unusable.The function should return:
-1 if no charging station is reachable from the startNode without using blockedRoads.[u, v], you can travel from u to v and from v to u.blockedRoad [u, v] means neither u -> v nor v -> u can be used.startNode itself is a charging station, the distance is 0.Examples
Example 1
Input:
n = 5, roads = [[0,1],[0,2],[1,3],[2,4]], startNode = 0, chargingStations = [3,4], blockedRoads = []
Output:
2
Note:
From node 0, both paths to 3 (via 1) and 4 (via 2) take 2 road segments. The shortest is 2.
Example 2
Input:
n = 5, roads = [[0,1],[0,2],[1,3],[2,4]], startNode = 0, chargingStations = [3], blockedRoads = [[0,1]]
Output:
-1
Note:
Road (0,1) is blocked. There is no alternative path from node 0 to node 3. Node 4 is not a charging station in this case.
Example 3
Input:
n = 3, roads = [[0,1],[1,2]], startNode = 0, chargingStations = [0,2], blockedRoads = []
Output:
0
Note:
The driver is already at a charging station (node 0), so 0 segments are needed.
Constraints
1 <= n <= 10000 <= roads.length <= n * (n - 1) / 20 <= startNode < n0 <= chargingStations.length <= n0 <= blockedRoads.length <= roads.lengthu, v, startNode, chargingStations elements) are between 0 and n-1 inclusive.[0,0]) or multiple roads between the same two intersections in roads.blockedRoads will only contain pairs that exist in roads.blockedRoads during traversal.blockedRoads to prevent invalid path segments.startNode being a charging station or no path existing.Loading editor...