问题1395--平面战争

1395: 平面战争

时间限制: 1 Sec  内存限制: 128 MB
提交: 20  解决: 7
[提交] [状态] [讨论版] [命题人:]

题目描述

A国正遭受敌人的袭击,敌国的军队已经到达Y城市。Y城市由N*M的方格组成。城市中所有的道路都是双向的,水平、垂直或者斜线方向的。在地图左上角是(0,0)点,右下角是(N,M)点。敌国军队现在到达(0,0)点,为了攻占A国,他们必须经过Y城市到达(N,M)点,下图是一个Y城市的交通图。 

每一个黑色顶点代表城市中的主要建筑群,他们之间有道路相连。在这些道路上面的数值表示炸毁该条道路所需要的TNT(炸药)。。。A国的防御部队已经无法抵御敌军的正面进攻,他们能做的就是通过炸毁道路阻止敌军通过Y城市而到达A国首都。现在作为A国国防部长,你需要决定炸毁哪些街道,使得敌军无法从(0,0)点到达(N,M)点,并且使用尽可能少的炸药。

输入

有多组测试数据。 
第一行两个正数N,M,表示地图的高和宽 
接下来N+1行,每行M个整数,依次对应该图中水平的道路 
接下来N行,每行M+1个整数,依次对应图中垂直的道路 
接下来2N行,每行2M个整数,依次对应图中斜线的道路。 


数据有多组,以EOF结束. (最后貌似有多余回车符,Pascal的童鞋可能会读到N=0,C++的直接无视)
数据范围: 
30%的数据1 <= N, M <= 50 
100%的数据: 
1 <= N, M <= 500 
1 <= amount <= 1,000,000

输出

输出一个整数,表示断开(0,0)点和(N,M)点所需的最少TNT数量。

样例输入 Copy

2 3
1 9 4
1 8 7
6 2 3
7 5 4 8
6 2 8 7
10 4 1 7 5 3
5 4 10 2 1 9
6 3 2 9 5 3
8 9 6 3 10 10

样例输出 Copy

18