Submit | All submissions | Best solutions | Back to list |
BINLADEN - Bin Laden |
English | Vietnamese |
Bin Laden the terrorist is hiding in a basement that has M floors below the ground. Each floor has N rooms. The rooms are separated by solid doors that are very hard to break. Each room has doors going to the room below and two rooms beside. From the ground, there are N doors going to N rooms of floor -1. Bin Laden is in the last floor (floor -M), room N (the rightmost room). Each door is made of diffrent kinds of metal, so they require different time to break.
Find the fastest way to go from the ground to Bin Laden's room or he will escape!
Input
- Line 1: M and N
- From line 2 to line 2M+1, even lines contain N numbers, odd lines contain N-1 numbers that are the time required to break the doors.
Output
A single number that is the minimum time to go to Bin Laden's room.
Example
Input 4 2 99 10 1 10 99 1 99 10 1 10 99 1 Output 44 +--99--+--10--+ | | | | 1 | | | | +--10--+--99--+ | | | | 1 | | | | +--99--+--10--+ | | | | 1 | | | | +--10--+--99--+ | | | | 1 | | | | +------+------+ We may go in zigzag.
Constraints
- 1 <= M <= 2222
- 1 <= N <= 10
- Time to break the doors is in [0, 1000].
Added by: | VOJ Team |
Date: | 2008-09-05 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
Resource: | VNOI Marathon '08 - Round 12/DivB Problem Setter: Lê Đôn Khuê |