问题 1676. -- 地道战

1676: 地道战

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 3
[提交][状态][讨论版]

题目描述

大家一定看过地道战的电视吧。 话说小兵张嘎有一回也跑去支援地道战了。那是河北的一个小镇里，这个小镇比较复杂，什么样的人都有。所以张嘎不能走大街，只能在地道里走。但根据地质情况不同，所以同样长的街道，地道里要走的时间可能不一样。当然每条街道下面都有地道，而且在街道连接处地道也有连接。有一天张嘎在A处，突然发现有大部队的敌军前来，所以他必须以尽快的速度跑到B处通知分队隐蔽，每条地道上都标出了他要走的时间。请帮他算一下，怎么走时间最短。 

               A +---2---+---3---+----1---+----2---+
                 |       |       |        |        |
                 2       1       2        2        3
                 |       |       |        |        |
                 +---2---+---3---+----4---+---5----+
                 |       |       |        |        |
                 3       4       1        2        3
                 |       |       |        |        |
                 +---2---+---2---+---1----+---4----+
                 |       |       |        |        |
                 2       2       1        3        4
                 |       |       |        |        |
                 +---1---+---3---+---2----+---3----+ B

输入

第1行输入2个整数N和M (1 <= n,m <=100)分别表示横向的街道的条数和纵向街道的条数。
以下n行每行输入各段地道（横向）需要的时间，每行按从左到右的顺序.
以下m行每行输入各段地道（纵向）需要的时间，每列按从上到下的顺序.

输出

输出一行，输出他从A到B的最短时间

样例输入

4 5
2 3 1 2
2 3 4 5
2 2 1 4
1 3 2 3
2 3 2
1 4 2
2 1 1
2 2 3
3 3 4

样例输出

13

提示

来源

动态规划

[提交][状态]