Fishmonger

Hard
0/120
Average time to solve is 30m
profile
Contributed by
11 upvotes
Asked in companies
SamsungAmazonProtiviti

Problem statement

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.
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 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
Sample Input 1 :
2
2 6
0 2
3 0
0 5
1 0
4 7
0 5 2 3
5 0 2 3
3 1 0 2
3 3 2 0
0 2 2 7
2 0 1 2
2 2 0 5
7 2 5 0
Sample Output 1:
5
6
Explanation :
In test case 1: 
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 5. Hence the answer is 5.

In test case 2:
The optimal path to reach node 3 from node 0 is 0 -> 2 -> 1 -> 3. The time required in the path is 6, and the minimum toll needed within the given time constraints is 6. Hence the answer is 6.
Sample Input 2 :
2
2 6
0 4
5 0
0 10
8 0
2 10
0 4
5 0
0 7
9 0
Sample Output 2 :
10    
7
Hint

Try to think of a recursive approach.

Approaches (2)
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.

  1. We will check If we reached the last node, then return the currToll. This will act as the base case of the recursive function.
  2. 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.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Fishmonger
Full screen
Console