Minimum time
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

Question

Minimum time

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

Accepted Answer

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.

Space Complexity: OtherExplanation:

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).

Time Complexity: O(n^n)Explanation:

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).

Accepted Answer

Dijkstra Algorithm

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.

Space Complexity: OtherExplanation:

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 priority queue. Hence, the overall space complexity is O(N + M).

Time Complexity: OtherExplanation:

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

The time complexity of insert, delete operation on priority queue is O(log(N)).

The time complexity of the Dijkstra Algorithm:

N times delete operation while extracting the minimum value vertex :O(N * log(N))

M times insert operation while traversing neighbor vertices: O(M*log(N))

Hence, the overall time complexity of the Dijkstra Algorithm is O((N+M)*log(N)).

Java (SE 1.8)


/*
	Time Complexity : O((N+M)*log(N))
	Space Complexity : O(N^2)
	
	where N is the number of vertices in the array, M is the number of edges in the graph.
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class The_Comparator implements Comparator> {
	public int compare(ArrayList str1, ArrayList str2) {
		int first_Str;
		int second_Str;
		first_Str = str1.get(0);
		second_Str = str2.get(0);
		if (first_Str == second_Str) {
			if (str1.get(1) > str2.get(0)) {
				return 1;
			}
		}
		if (first_Str > second_Str) {
			return 1;
		} else {
			return -1;
		}
	}
}

public class Solution {
	public static int minCost(ArrayList>> graph, int src, int des, int n, int[] p,
			int currCost) {

		// Array to check whether particular vertex is visited or not
		boolean visited[] = new boolean[n];

		// Make a min priority queue
		PriorityQueue> pq = new PriorityQueue<>(new The_Comparator());
		pq.add(new ArrayList<>(Arrays.asList(0, src)));

		while (!pq.isEmpty()) {
			
			// Access the top pair of min priority queue
			ArrayList topPair = pq.poll();
			int currDist = topPair.get(0);
			int currIndex = topPair.get(1);

			if (visited[currIndex] == true) {
				continue;
			}

			// Mark currIndex as visited
			visited[currIndex] = true;

			// If we reached destination then return minimum cost
			if (currIndex == des) {
				return currDist;
			}

			currCost = currDist;

			// Check whether light is green when we reach at that node
			if (currCost != 0 && (currCost % p[currIndex]) != 0) {
				int temp = currCost % p[currIndex];
				currCost = currCost + (p[currIndex] - temp);
			}

			for (int i = 0; i < graph.get(currIndex).size(); i++) {
				pq.add(new ArrayList<>(Arrays.asList(currCost + graph.get(currIndex).get(i).get(1),
						graph.get(currIndex).get(i).get(0))));
			}
		}

		// Return -1 when we cannot reach the destination
		return -1;
	}

	public static int findMinCost(int[][] edges, int n, int m, int src, int dest, int[] p) {

		// Maintain an adjacency list of edges
		ArrayList>> graph = new ArrayList<>(n);

		// Initialization
		for (int i = 0; i < n; i++) {
			ArrayList> temp = new ArrayList<>();
			graph.add(temp);
		}

		for (int i = 0; i < m; i++) {
			graph.get(edges[i][0]).add(new ArrayList<>(Arrays.asList(edges[i][1], edges[i][2])));
			graph.get(edges[i][1]).add(new ArrayList<>(Arrays.asList(edges[i][0], edges[i][2])));
		}

		// Return the minimum cost to reach the destination
		return minCost(graph, src, dest, n, p, 0);
	}

}

C++ (g++ 5.4)

/*

Time Complexity : O((N+M)*log(N))

Space Complexity : O(N^2)



where N is the number of junctions and M is the number of roads

*/



#include 



class myComparator 

{

    public:



        bool operator()(vector &p1, vector &p2) 

        {

            return p1[0] > p2[0];

        }

};



int minCost(vector>> &graph, int src, int des, int n, vector &p, int currCost)

{   

    // Array to check whether particular vertex is visited or not

    vector visited(n, false);



    // Make a min priority queue

    priority_queue, vector>, myComparator> pq;

    pq.push({0, src});



    while(pq.empty() == false)

    {

        // Access the top pair of min priority queue

        vector topPair = pq.top(); 

        pq.pop();

        int currDist = topPair[0];

        int currIndex = topPair[1];



        if(visited[currIndex] == true)

        {

            continue;

        }

        

        // Mark currIndex as visited

        visited[currIndex] = true;

        

        // If we reached destination then return minimum cost

        if(currIndex == des)

        {

            return currDist;

        }



        int currCost = currDist;



        // Check whether light is green when we reach at that node

        if(currCost != 0 and (currCost % p[currIndex]) != 0)

        {

            int temp = currCost % p[currIndex];

            currCost = currCost + (p[currIndex] - temp);

        }

        

        for(int i = 0; i < graph[currIndex].size(); i++)

        {

            pq.push({currCost + graph[currIndex][i][1], graph[currIndex][i][0]});

        }

    }



    // Return -1 when we cannot reach the destination

    return -1;

}



int findMinCost(vector> &edges, int n, int m, int src, int des, vector &p) 

{    

    // Maintain an adjacency list of edges

    vector>> graph(n);



    for(int i = 0; i < m; i++)

    {

        graph[edges[i][0]].push_back({edges[i][1], edges[i][2]});

        graph[edges[i][1]].push_back({edges[i][0], edges[i][2]});

    }

    

    // Return the minimum cost to reach the destination

    return minCost(graph, src, des, n, p, 0);

}

Python (3.5)

"""

Time Complexity : O((N+M)*log(N))

Space Complexity : O(N^2)



where N is the number of junctions and M is the number of roads

"""



from queue import PriorityQueue



def minCost(graph, src, des, n, p, currCost):

    

    # Array to check whether particular vertex is visited or not

    visited = [False for i in range(n)]



    # Make a min priority queue

    pq = PriorityQueue()

    pq.put((0, src))



    while(pq.empty() == False):



        # Access the top pair of min priority queue

        topPair = pq.get()

        currDist = topPair[0]

        currIndex = topPair[1]



        if(visited[currIndex] == True):

            continue

        

        # Mark currIndex as visited

        visited[currIndex] = True

        

        # If we reached destination then return minimum cost

        if(currIndex == des):

            return currDist



        currCost = currDist



        # Check whether light is green when we reach at that node

        if(currCost != 0 and (currCost % p[currIndex]) != 0):

            temp = currCost % p[currIndex]

            currCost = currCost + (p[currIndex] - temp)

        

        for i in range(0, len(graph[currIndex])):

            pq.put((currCost + graph[currIndex][i][1], graph[currIndex][i][0]))



    # Return -1 when we cannot reach the destination

    return -1



def findMinCost(edges, n, m, src, des, p):

    

    # Maintain an adjacency list of edges

    graph = [[] for i in range(n)]



    for i in range(0, m):



        graph[edges[i][0]].append((edges[i][1], edges[i][2]))

        graph[edges[i][1]].append((edges[i][0], edges[i][2])) 



    # Return the minimum cost to reach the destination

    return minCost(graph, src, des, n, p, 0)