F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4676. -- Xor-Mul棋盘

4676: Xor-Mul棋盘

Time Limit: 15 Sec  Memory Limit: 256 MB
Submit: 85  Solved: 45
[Submit][Status][Discuss]

Description

一个n*m的棋盘,左上角为(1,1),右下角为(n,m)。相邻的2点之间有连边
(如下图中实线)特殊地,(1,i)与(n,i)也连有一条边(如下图中虚线),i=1..m。
如下图,就是一个n=3,m=4的棋盘。
每个点(i,j)给定2个值a[i][j],b[i][j]。每条边e给定1个值c[e]。
你的任务是给每一个点一个非负的d值,最小化(S1+S2)。

Input

第一行2个整数n,m。
接着n行,每行m个数,其中第i行第j个数表示a[i][j]。
接着n行,每行m个数,其中第i行第j个数表示b[i][j]。
接着n行,每行m-1个数,其中第i行第j个数表示(i,j)与(i,j+1)的边的c值。
接着n-1行,每行m个数,其中第i行第j个数表示(i,j)与(i+1,j)的边的c值。
最后一行m个数,其中第i个数表示(1,i)与(n,i)的边的c值。
2<=n<=5, 1<=m<=10000
a,b,c 的值均为不大于 10^6 的正整数

Output

一个整数,表示S1+S2的最小值

Sample Input

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

Sample Output

49

HINT

Source

[Submit][Status][Discuss]

HOME Back