记录编号	60569	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	SpaceQ	是否通过	通过
代码语言	C++	运行时间	0.237 s
提交时间	2013-05-26 18:56:44	内存使用	20.34 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#include<vector>
#include<iostream>
//#include<WJMZBMR>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define maxn 1000000

int s,t,n,m;
inline int idu(int i,int j)
{
	if(i==0)return s;
	return (i-1)*(m-1)+j;
}
inline int idd(int i,int j)
{
	if(i==n-1)return t;
	return i*(m-1)+j;
}
inline int idr(int i,int j)
{
	if(j==m-1)return s;
	return i*(m-1)+j;
}
inline int idl(int i,int j)
{
	if(j==0)return t;
	return i*(m-1)+j-1;
}
struct edge
{
	int to,c;
};
vector<edge>G[maxn];
void add(int from,int to,int c)
{
	G[from].pb((edge){to,c});
	G[to].pb((edge){from,c});
}
long long d[maxn];
bool v[maxn];
struct state
{
	int p;
	bool operator<(const state&o)const
	{
		return d[p]>d[o.p];
	}
};

priority_queue<state>Q;
void dij()
{
	memset(d,127,sizeof(d));
	memset(v,0,sizeof(v));

	d[s]=0;
	Q.push((state){s});

	while(Q.size())
	{
		int x=Q.top().p;Q.pop();
		if(v[x])continue;
		v[x]=true;
		rep(i,G[x].size())
		{
			edge&e=G[x][i];
			if(d[e.to]>d[x]+e.c)
			{
				d[e.to]=d[x]+e.c;
				Q.push((state){e.to});
			}
		}
	}
}
	
int main()
{
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	int T,a;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		s=(n-1)*(m-1);t=s+1;
		rep(i,n*m+3)G[i].clear();
		rep(i,n)rep(j,m-1)
		{
			scanf("%d",&a);
			add(idu(i,j),idd(i,j),a);
		}
		rep(i,n-1)rep(j,m)
		{
			scanf("%d",&a);
			add(idr(i,j),idl(i,j),a);
		}
		dij();
		long long ans=d[t];
		cout<<ans<<endl;
	}
	return 0;
}