记录编号	98494	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2014-04-23 14:35:27	内存使用	0.60 MiB

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>

using namespace std;

typedef unsigned long long LL;

const LL MAXN=110*110;
const LL INF=LL(10000)*10000*10000;

struct edge{
	LL to,cost;
};

LL N,M;

struct spfa{
	vector<edge> edges;
	vector<int> G[MAXN];
	
	LL s,t;
	
	void init(){
		s=t=0;
		edges.clear();
		for(int i=0;i<MAXN;i++)G[i].clear();
	}
	
	void add_edge(int from,int to,int cost){
		//cout<<from<<" "<<to<<" "<<cost<<endl;
		edges.push_back((edge){to,cost});
		edges.push_back((edge){from,cost});
		LL m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	LL d[MAXN];bool inq[MAXN];
	int inq_t[MAXN];
	LL min_cost(){
		for(int i=0;i<MAXN;i++)d[i]=INF;
		memset(inq,0,sizeof(inq));
		memset(inq_t,0,sizeof(inq_t));
		queue<LL> q;
		q.push(s);inq[s]=true;
		d[s]=0;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			inq_t[u]++;
			if(inq_t[u]%1000==0){
				cout<<inq_t[u]<<endl;
			}
			for(LL i=0;i<G[u].size();i++){
				edge & e=edges[G[u][i]];
				if(d[e.to]>d[u]+(LL)e.cost){
					d[e.to]=d[u]+(LL)e.cost;
					if(!inq[e.to]){
						inq[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
		return d[t];
	}
}solver;

int cal_num(int x,int y){//方块 坐标 
	int n=N-1;
	int m=M-1;
	if(x==0 || y>m)return 0;
	if(x>n || y==0)return (N-1)*(M-1)+1;
	return (x-1)*n+y;
}

int cal_left_down(int x,int y){
	x=x+1;
	return cal_num(x,y);
}

int cal_right_down(int x,int y){
	x=x+1;y=y+1;
	return cal_num(x,y);
}

int cal_right_up(int x,int y){
	y=y+1;
	return cal_num(x,y);
}

void read_and_build(){
	solver.init();
	scanf("%lld %lld",&N,&M); 
	//H(N*(M-1)),V((N-1)*M)，H[i][j]表示(i,j)->(i,j+1)的流量；
	for(int i=0;i<N;i++){
		for(int j=0;j<M-1;j++){
			LL cost;scanf("%lld",&cost);
			int u=cal_right_up(i,j);
			int v=cal_right_down(i,j);
			solver.add_edge(u,v,cost); 
		}
	}
	
	for(int i=0;i<N-1;i++){
		for(int j=0;j<M;j++){//V[i][j]表示(i,j)->(i+1,j)的流量
			LL cost;scanf("%lld",&cost);
			int u=cal_left_down(i,j);
			int v=cal_right_down(i,j);
			solver.add_edge(u,v,cost); 
		}
	}
	solver.s=0;solver.t=(N-1)*(M-1)+1;
}

void solve(){
	read_and_build();
	LL ans=solver.min_cost();
	printf("%lld\n",ans);
}

int main(){
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	//freopen("in.txt","r",stdin);
	int T;scanf("%d",&T);
	while(T-->0){
		solve();
	}
	return 0;
}