Minimum Time

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
6 upvotes
Asked in companies
AppleRubrik, Inc.Novus Platform

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 5
4 3 2 5
0 1 4
0 2 8
1 2 6
1 3 10
2 3 7
0 3
3 3
2 3 4
0 1 5
1 2 4
0 2 2
0 2
Sample Output 1 :
15
2
Explanation :
In test case 1:
The path 0 -> 1 -> 3 takes time 4 + 2 (wait till 6) + 10 = 16.
The path 0 -> 2 -> 3 takes time 8 + 0 (no wait) + 7 = 15.
The path 0 -> 1 -> 2 -> 3 takes time 4 + 2 (wait till 6) + 6 + 0 (no wait) + 7 = 19.
The path 0 -> 2 -> 1 -> 3 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
Hence the answer is 15.

In test case 2:
The path 0 -> 2 takes time 2 as there is the direct edge of weight 2. Hence the answer is 2.
Sample Input 2:
1
3 1
3 2 6
0 1 9
0 2
Sample output 2:
-1
Hint

Try to think of a Depth First Search approach.

Approaches (2)
Depth First Search

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.
Time Complexity

O(N^N) where N is the number of junctions.
 

For each vertex, we are making N recursive calls. For N vertices, the time complexity will be O(N^N). Hence, the overall time complexity is O(N^N).

Space Complexity

O(N + M), where N is the number of junctions and M is the number of roads.

 

The space complexity O(N + M) is needed to make the adjacency list of edges. The space complexity O(N) is needed for the visited array and recursion stack in the worst case. Hence, the overall space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Minimum Time
Full screen
Console