Last Updated: 12 Dec, 2020
Fishmonger
Hard
Asked in companies
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
Approaches
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.
- If visited[ind] is false and difference of M and Time[currIndex][ind] is greater than or equal to 0 then
- 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.
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.