Last Updated: 11 Dec, 2020
Minimum Time
Moderate
Asked in companies
There are ‘N’ junctions connected by ‘M’ bi-directional roads. At most, one road is present between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the same in both directions.
A vehicle at a junction can start moving along a road only when the light at the current junction flashes green. If a vehicle arrives at a junction between green flashes, it must wait for the next green flash before continuing in any direction. If it arrives at a junction exactly when the light flashes green, it can immediately proceed along any road originating from that junction.
You are given a city map that shows travel times for all roads. For each junction ‘i’, you are given ‘P[i]’, the time period between green flashes of the light at that junction. The light at junction ‘i’ flashes green at times 0, P[i], 2P[i], 3P[i] and so on.
Your task is to return the minimum time taken from a given source junction ‘src’ to a given destination junction ’des’ for a vehicle when the traffic starts. The junctions are identified by integers ‘0’ through ‘N - 1’. If we cannot reach the destination junction, then return -1.
For example:
Consider if ‘N’ = 3 and edges are
[[0, 1, 2],
[1, 2, 4]]
'P' = [2, 3, 4], and we have to reach from junction 0 to 2.
The time consumed from junction 0 to 1 is 2. We have to wait for 1 for the next green flash at junction 1. The time consumed from junction 1 to 2 is 4. The path 0 -> 1 -> 2 takes time 2 + 1 (wait till 3) + 4 = 7. Hence, the answer is 7.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of junctions and roads.
The next line contains ‘N’ space-separated integers denoting the elements of the array ‘P’ elements where ‘P[i]’ is the time needed at junction ‘i’ for light to turn green.
The next ‘M’ lines of each test case contain three space-separated integers denoting the road between ‘Edges[i][0]’ and ‘Edges[i][1]’ junctions with ‘Edges[i][2]’ denoting the time to travel the road.
The last line of each test case contains two space-separated integers, 'src' and 'des', denoting the source and destination junctions.
Output Format :
For each test case, print a single integer that denotes the minimum time needed from the junction ‘src’ to ‘des’. Print ‘-1’ in case we cannot reach the ‘des’ junction.
Print the output of each test case in a separate line.
Constraints
1 <= T <= 5
2 <= N <= 10^5
1 <= M <= 10^5
1 <= P[i] <= 10^7
0 <= Edges[i][0] , Edges[i][1] < N
1 <= Edges[i][2] <= 10^7
0 <= src, des < ‘N’
Time limit: 1 sec
Approaches
This approach will use DFS(Depth First Search) to make a recursive function in which we pass the currCost, which is the current cost. If the light is not green when we reach that junction, we have to add the waiting time in currCost. After that, we will call the recursive function on all the adjacent unvisited junctions by incrementing the currCost with the weight of the edge. We will maintain a variable minVal to store the minimum cost that is returned from the recursive calls. In the end, we will return the variable minVal.
Algorithm:
- Make a recursive function minCost(graph, src, des, visited, p, currCost) where graph is adjacency list of edges, p is an array containing time period for each index, currCost is cost till this node. This function returns the minimum cost needed to reach des junction from the src junction.
- The base condition of this function is if we reach the des junction means src is equal to des, then return currCost.
- Set visited[src] as true.
- If currCost is not 0 and p[src] is not factor of currCost then
- Set temp as remainder of currCost divided by p[src].
- Increment currCost by the difference of p[src] and temp.
- Set minVal as a large integer value.
- Iterate over all the adjacent vertices of src vertex using an adjacency list graph. We will iterate i from 0 to the size of graph[src].
- Set adjVetex as graph[src][i][0] and weight as graph[src][i][1].
- If visited[adjVetex] is true, then move to the next adjacent vertex. else
- Call the function minCost(graph, adjVertex, des, visited, p, currCost + weight) for adjacent vertex and update the minVal with a minimum value of minVal and value returned by the recursive call.
- Set visited[src] as false.
- Return minVal, which is the minimum cost needed to reach the destination from the source.
- Make a findMinCost(edges, N, M, src, des, p) function that returns the minimum cost needed to reach the des junction from the src junction.
- Make a visited array of size N and initialize its values with false.
- Make an adjacency list graph of edges where each index contains the list of pairs with pair values as adjacent vertex and weight of that edge.
- Iterate i from 0 to M-1
- Insert an array of edges[i][1] and edges[i][2] in graph[edges[i][0]].
- Insert an array of edges[i][0] and edges[i][2] in graph[edges[i][1]].
- Set result as the value returned by minCost(graph, src, des, visited, p, 0) function.
- Check If visited[des] is true, then return result. Otherwise, return -1.
In this approach, we will use the Dijkstra Algorithm to solve the problem. We will make a visited array and a min priority queue of pairs of integers where the first element in the pair is cost and the second element is vertex number. So initially, we insert a pair of 0 and src in our min priority queue pq, then run a loop until pq is not empty. We delete the front pair in the loop and then insert the adjacent vertices in the queue pq. If the front pair has des as its vertex means we reach the des, then return the first element of the queue’s front pair, which is the minimum cost to reach des from src.
Algorithm:
- Make a function minCost(graph, src, des, N, p, currCost) where graph is adjacency list of edges, p is an array containing time period for each index, currCost is cost till this node. This function returns the minimum cost needed to reach des junction from the src junction.
- Create a visited array of size N and initialize all its elements with false.
- Create a min priority queue of pair of integers pq.
- Insert a pair [0,src] in pq.
- Run a loop while pq is not empty.
- Set topPair as the front pair element of pq.
- Set currDist as the first value of topPair.
- Set currIndex as the second value of topPair.
- Delete the front element of pq.
- If visited[currIndex] is true, continue the loop.
- Set visited[currIndex] as true.
- If currIndex is equal to des
- We will return currDist.
- Set currCost as currDist.
- If currCost is not 0 and p[currIndex] is not factor of currCost then
- Set temp as remainder of currCost divided by p[currIndex].
- Increment currCost by the difference of p[currIndex] and temp.
- Iterate over all the adjacent vertices of currIndex:
- Insert a pair of cost and adjacent vertex. We will insert [currCost + weight of edge , adjacent vertex] in pq.
- Return -1 means there is no path from src to des.
- Make a findMinCost(edges , N, M, src, des, p) function that returns the minimum cost needed to reach the des junction from the src junction.
- Make an adjacency list of edges where each index contains the list of pairs with pair values as adjacent vertex and the weight of that edge.
- Iterate i from 0 to M-1
- Insert an array of edges[i][1] and edges[i][2] in graph[edges[i][0]].
- Insert an array of edges[i][0] and edges[i][2] in graph[edges[i][1]].
- Return the value returned by the minCost(graph,src, des, N, p, 0) function.