MISERMAN - Wise And Miser
Jack is a wise and miser man. Always tries to save his money.
One day, he wants to go from city A to city B. Between A and B, there are N number of cities (including B and excluding A) and in each city there are M buses numbered from 1 to M. And the fare of each bus is different. Means for all N×M buses, fare (K) may be different or same. Now Jack has to go from city A to city B following these conditions:
- At every city, he has to change the bus.
- And he can switch to only those buses which have number either equal or 1 less or 1 greater to the previous.
You are to help Jack to go from A to B by spending the minimum amount of money.
N, M, K <= 100.
Input
Line 1: N M
Line 2: N×M Grid
Each row lists the fares the M busses to go form the current city to the next city.
Output
Single Line containing the minimum amount of fare that Jack has to give.
Example
Input: 5 5 1 3 1 2 6 10 2 5 4 15 10 9 6 7 1 2 7 1 5 3 8 2 6 1 9 Output: 10
Explanation
1 → 4 → 1 → 3 → 1: 10
hide comments
ameyanator:
2018-01-23 19:18:51
Simple table filling question :') |
|
surajmall:
2017-10-22 22:33:07
dp for beginners for start dp :)
|
|
prince kumar:
2017-04-04 21:29:13
same as BYTESM2 but it hasn't got c++4.3.2 option. Submitted same code (with option c++(gcc6.3) )and got WA in BYTESM2 but AC in MISERMAN (with option c++(gcc4.3.2) ) . Can't figure out difference in the option selected as both are c++!! |
|
rishabh_nitw:
2017-03-23 10:28:54
BottomUp DP Easiest :P Read Multistage Graph |
|
vladimira:
2017-03-16 05:32:59
Easiest dp. |
|
nilabja16180:
2017-03-06 18:37:01
DP is great!
|
|
shahzada:
2017-03-06 15:26:37
Easiest DP problem. AC- 0.00s Last edit: 2017-03-06 15:26:59 |
|
vineetpratik:
2017-02-27 15:39:21
Same as philosopher's stone |
|
scorpion_ajay:
2017-02-25 19:41:10
try philosphors stone before this one..... though both are same;
|
|
vengatesh15:
2017-01-18 16:16:03
Simple one.. |
Added by: | The quick brown fox jumps over the lazy dog |
Date: | 2010-10-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC VB.NET |
Resource: | Udit Agarwal |