FISHER  Fishmonger
A fishmonger wants to bring his goods from the port to the market. On his route he has to traverse an area with many tiny city states. Of course he has to pay a toll at each border.
Because he is a good business man, 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 certain time, otherwise his fish start to smell.
Input
The first line contains the number of states n and available time t. The first state is the port, the last state is the market. After this line there are n lines with n numbers each, specifying for each state the travel time to the ith state. This table is terminated with an empty line. The table of the tolls follows in the same format.
n is at least 3 and at most 50. The time available is less than 1000. All numbers are integers.
There are many test cases separated by an empty line. Input terminates with number of states and time equal 0 0.
Output
For each test case your program should print on one line the total amount of tolls followed by the actual travelling time.
Example
Sample input: 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 0 0 Sample output: 6 6
This corresponds to the following situation, the connections are labeled with (time, toll):
hide comments
thanos_tapras:
20200430 17:54:38
Nice dp on graph 

anandksbiw:
20200130 12:53:42
what is the approach of solving this problem using dijkstra algo? 

dkkv0000:
20200121 13:16:26
01 knapsack 

sandeepd:
20191211 18:14:00
Nice problem. Last edit: 20191211 18:14:13 

aritra741:
20190719 09:18:56
Could anyone suggest more problems like this? 

aarls:
20190717 18:28:55
can anyone tell how to do this with (DP Knapsack)...? Last edit: 20190718 07:41:54 

lamia2658:
20180829 10:33:00
shortest path makes it easy.. ;) 

amulyagaur:
20171219 06:02:51
submit the same code for FPOLICE also and get 2 ACs within few seconds :) 

shubham808:
20170715 14:05:14
AC in 1 go !! *) 

youssef20:
20170416 12:05:48
:) \n

Added by:  MichaĆ Czuczman 
Date:  20040707 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Swiss Olympiad in Informatics 2004 