Fishmonger
A fishmonger wants to bring his goods from port to the market. On his route, he has to traverse an area with many states. He has to pay a toll at each border.

He is a good businessman. He wants to choose the route in such a way that he has to pay as little money for tolls as possible. On the other hand, he has to be at the market within a particular time. Otherwise, his fish will start to smell.

You are given ‘N’ number of states and the time ‘M’ in which he has to reach the market. You need to return the minimum toll amount that he has to pay to reach the market in the given time. The 0’th index is the port, and the 'N'-1 index is the market.

For example:

Consider If N = 2 , M = 4, Time = [[0, 2], [3, 0]] and Toll = [[0, 10], [ 5, 0]]] The optimal path to reach node 1 from node 0 is 0 - 1. The time required in the path is 2, and the minimum toll needed within the given time constraints is 10. Hence the answer is 10.

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 states and given time limit. The next ‘N’ line contains ‘N’ space-separated integers denoting the elements of the array ‘Time’ where ‘Time[i][j]’ represents the time needed to traverse from state ‘i’ to state ‘j’. The next ‘N’ line contains ‘N’ space-separated integers denoting the elements of the array ‘Toll’ where ‘Toll[i][j]’ represents the toll needed to traverse from state ‘i’ to state ‘j’.

Output Format :

For each test case, print the minimum toll needed to reach the market from the port. If we cannot reach the market within the given time limit, then print -1. Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Fishmonger

A fishmonger wants to bring his goods from port to the market. On his route, he has to traverse an area with many states. He has to pay a toll at each border.

He is a good businessman. He wants to choose the route in such a way that he has to pay as little money for tolls as possible. On the other hand, he has to be at the market within a particular time. Otherwise, his fish will start to smell.

You are given ‘N’ number of states and the time ‘M’ in which he has to reach the market. You need to return the minimum toll amount that he has to pay to reach the market in the given time. The 0’th index is the port, and the 'N'-1 index is the market.

For example:

Consider If N = 2 , M = 4, Time = [[0,  2], [3,  0]] and Toll = [[0, 10], [ 5,  0]]]
The optimal path to reach node 1 from node 0 is 0 -> 1. The time required in the path is 2, and the minimum toll needed within the given time constraints is 10. Hence the answer is 10.

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 states and given time limit.

The next ‘N’ line contains ‘N’ space-separated integers denoting the elements of the array ‘Time’ where ‘Time[i][j]’ represents the time needed to traverse from state ‘i’ to state ‘j’.

The next ‘N’ line contains ‘N’ space-separated integers denoting the elements of the array ‘Toll’ where ‘Toll[i][j]’ represents the toll needed to traverse from state ‘i’ to state ‘j’.

Output Format :

For each test case, print the minimum toll needed to reach the market from the port. If we cannot reach the market within the given time limit, then print -1. 

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
2 <= N <= 50
1 <= M <= 1000
0 <= Toll[i] <= 10^8
0 <= Time[i] <= 1000

Time limit: 1 sec

Accepted Answer

Brute Force

In this approach, we have to make a recursive function that returns the minimum toll needed to reach the N-1 node within the given time limit. We have to create a visited array of size N to maintain which vertices are already visited.

We will check If we reached the last node, then return the currToll. This will act as the base case of the recursive function.
We will call the recursive function on all the adjacent unvisited nodes and also within the given time limit. We will maintain a minVal variable that finds the minimum value from all these function calls. In the end we will return the minVal, which is the minimum toll value needed to reach N-1 node.

We will define a function dfs(N, M, Time, Toll, currToll, currIndex, visited) where N is the number of states, M is the time limit, Time is the time matrix, Toll is the toll matrix, currToll is the toll value calculated till now, currIndex is the current index, and visited is the array to check which indices are visited.

Algorithm:

Make a recursive function dfs(N, M, Time, Toll, currToll, currIndex, visited). This function returns the minimum Toll needed to reach the last vertex from the first vertex.
- The base condition of this function is if currIndex is equal to N-1, then return currToll.
- Set minVal as a large value.
- Set visited[currIndex] as True.
- Iterate ind from 0 to N-1:
  - If visited[ind] is false and difference of M and Time[currIndex][ind] is greater than or equal to 0 then
    - Set currVal as value returned by calling dfs(N, M - Time[currIndex][ind] , Time, Toll, currToll + Toll[currIndex][ind] , ind, visited).
    - If currVal is less than minVal then update minVal as currVal.
- Set visited[currIndex] as False.
- Return minVal.
Make a function findToll(N, M, Time, Toll). This function returns an integer corresponding to the minimum toll needed within given time constraints.
- Make a visited array of size N and initialize all its elements with false.
- Set result as the value returned by dfs(N, M, Time, Toll, 0, 0, visited).
- If the result is still a large integer value, return -1.
- Return the variable result.

Space Complexity: O(n^2)Explanation:

O(N) where N is the number of states.

The space complexity O(N) is needed to make the visited array. The space complexity O(N) is also needed for the recursion stack in the worst case. Hence, the overall space complexity is O(N).

Time Complexity: O(n^n)Explanation:

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

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

Breadth-First Search

In this approach, we have to maintain a 2d array dist in which dist[i][j] stores the minimum Toll needed to reach index i within the j time limit. We have to make a queue q that we will use to fill this dist array. The queue q stores the array consisting of 3 elements denoting the vertex, time, and toll required to travel to that vertex. Initially insert [0, 0, 0] in the queue and set dist[0][0] as 0. We will iterate till the queue is not empty, and in each iteration, we will traverse through each vertex. We have to maintain a result variable that stores our actual answer. In the end, we will return the variable result.

Algorithm:

Make a function findToll(N, M, Time, Toll). This function returns the minimum Toll needed to reach the last vertex from the first vertex.
- Make a 2d array dist with size N+1 rows and M+1 columns and initialize all its elements with a large integer value.
- Make a queue q that stores the array consisting of 3 elements denoting the vertex, time, and toll required to travel to that vertex.
- Insert [0, 0, 0] in the queue.
- Set dist[0][0] as 0.
- Set result as a large integer value.
- Iterate till q is not empty.
  - Set temp as the front element of the queue.
  - Set first as the first element of temp.
  - Set second as the second element of temp.
  - Set third as the third element of the temp.
  - Delete the first element from the queue.
  - Run a loop of ind from 0 to N-1.
    - If ind is equal to first or the sum of second and Time[first][ind] is greater than M, then we will move to the next vertex.
    - If dist[ind][second + Time[first][ind]] is greater than sum of third and Toll[first][ind].
      - Set dist[ind][second + Time[first][ind]] as sum of third and Toll[first][ind].
      - Insert [ind, second + Time[first][ind], third + Toll[first][ind]] in queue.
      - If ind is equal to N-1, then set the result as the minimum of result and sum of third and Toll [first][ind].
- If the result is still a large integer value.
  - Return -1.
- Return result, which is the minimum Toll needed within a given time.

Space Complexity: OtherExplanation:

O(N*M) where N is the number of states and M is the given time limit.

The space complexity O(N*M) is needed to make the distance array. The space complexity O(N*M) is also required to maintain the queue. Hence, the overall space complexity is O(N*M).

Time Complexity: OtherExplanation:

O((N^2)*M) where N is the number of states and M is the given time limit.

In the worst case, we are doing N*M iterations and in each iteration, we are traversing through all the N vertices that take O(N) time. Hence, the overall time complexity is O((N^2)*M).

Java (SE 1.8)


/*
	Time Complexity: O((N^2)*M)
	Space Complexity: O(N*M)
	
	where N is the number of states and M is the given time limit.
*/
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

	public static int findToll(int n, int m, int[][] time, int[][] toll) {

		// Make dist array with n+1 rows and m+1 columns
		int[][] dist = new int[n + 1][];
		for (int i = 0; i < n + 1; i++) {
			int temp[] = new int[m + 1];
			Arrays.fill(temp, Integer.MAX_VALUE);
			dist[i] = temp;
		}
		// Make a queue q
		Queue q = new LinkedList<>();
		int tempArr[] = { 0, 0, 0 };
		q.add(tempArr);
		dist[0][0] = 0;

		// Set result as large integer value
		int result = Integer.MAX_VALUE;

		// Iterate while q is not empty
		while (!q.isEmpty()) {
			
			// Get the first element of queue
			int[] temp = q.poll();

			int first = temp[0];
			int second = temp[1];
			int third = temp[2];

			// Iterate ind from 0 to n-1
			for (int ind = 0; ind < n; ind++) {
				if (ind == first || second + time[first][ind] > m) {
					continue;
				}

				if (dist[ind][second + time[first][ind]] > third + toll[first][ind]) {
					// Update the dist array
					dist[ind][second + time[first][ind]] = third + toll[first][ind];
					int temp2[] = { ind, second + time[first][ind], third + toll[first][ind] };
					q.add(temp2);

					if (ind == n - 1) {
						// Update result variable
						result = Math.min(result, third + toll[first][ind]);
					}
				}
			}
		}

		// If we cannot reach last index within given time limit
		if (result == Integer.MAX_VALUE) {
			return -1;
		}

		// Return minimum toll value needed to read last index
		return result;
	}

}

C++ (g++ 5.4)

/*

Time Complexity: O((N^2)*M)

Space Complexity: O(N*M)



where N is the number of states and M is the given time limit.

*/



#include 

#include 



int findToll(int n, int m, vector> &time, vector> &toll) 

{    

    // Make dist array with n+1 rows and m+1 columns

    vector> dist(n + 1, vector(m + 1, INT_MAX));

    

    // Make a queue q

    queue> q;

    

    q.push({0, 0, 0});

    dist[0][0] = 0;

    

    // Set result as large integer value 

    int result = INT_MAX;

    

    // Iterate while q is not empty

    while(q.empty() == false)

    {   

        // Get the first element of queue

        vector temp = q.front(); 

        q.pop();

        

        int first = temp[0];

        int second = temp[1];

        int third = temp[2];

        

        // Iterate ind from 0 to n-1

        for(int ind = 0; ind < n; ind++)

        {   

            if(ind == first || second + time[first][ind] > m)

            {

                continue;

            }

            

            if(dist[ind][second + time[first][ind]]  > third + toll[first][ind])

            {   

                // Update the dist array

                dist[ind][second + time[first][ind]] = third + toll[first][ind];

                

                q.push({ind, second + time[first][ind], third + toll[first][ind]});

                

                if(ind == n - 1)

                {   

                    // Update result variable 

                    result = min(result, third + toll[first][ind]);

                }

            }

        }

    }

    

    // If we cannot reach last index within given time limit         

    if(result == INT_MAX)

    {

        return -1;

    }

            

    // Return minimum toll value needed to read last index

    return result;

}

Python (3.5)

"""

Time Complexity: O((N^2)*M)

Space Complexity: O(N*M)



where N is the number of states and M is the given time limit.

"""



from sys import maxsize

import queue



def findToll(n, m, time, toll):

    

    # Make dist array with n+1 rows and m+1 columns

    dist = [[maxsize for j in range(m + 1)] for i in range(n + 1)]

    

    # Make a queue q

    q = queue.Queue()

    

    q.put((0, 0, 0))

    dist[0][0] = 0

    

    # Set result as large integer value 

    result = maxsize

    

    # Iterate while q is not empty

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

        

        # Get the first element of queue

        temp = q.get()

        

        first = temp[0]

        second = temp[1]

        third = temp[2]

        

        # Iterate ind from 0 to n-1

        for ind in range(0, n):

            

            if(ind == first or (second + time[first][ind] > m)):

                continue

            

            if(dist[ind][second + time[first][ind]]  > third + toll[first][ind]):

                

                # Update the dist array

                dist[ind][second + time[first][ind]] = third + toll[first][ind]

                

                q.put((ind, second + time[first][ind], third + toll[first][ind]))

                

                if(ind == n - 1):

                    

                    # Update result variable 

                    result = min(result, third + toll[first][ind])

    

    # If we cannot reach last index within given time limit         

    if(result == maxsize):

        return -1

            

    # Return minimum toll value needed to read last index

    return result