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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int SIZEn=110,SIZEN=10100;
const ll INF=1e16;
int N;//0到N
int n,m;
int S,T;
vector<pair<int,ll> > c[SIZEN];
queue<int> Q;
bool inq[SIZEN];
void SPFA(vector<pair<int,ll> > c[SIZEN],int S,int T,ll f[SIZEN]){
	for(int i=0;i<=N;i++) f[i]=INF;
	while(!Q.empty()) Q.pop();
	memset(inq,0,sizeof(inq));
	f[S]=0;inq[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int v=c[x][i].first;
			if(f[x]+c[x][i].second<f[v]){
				f[v]=f[x]+c[x][i].second;
				if(!inq[v]){
					inq[v]=true;
					Q.push(v);
				}
			}
		}
	}
}
int hash(int x,int y){
	return x*m+y;
}
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
	c[b].push_back(make_pair(a,w));
}
ll f[SIZEN];
void work(void){
	if(n==1&&m==1){
		printf("0\n");
		return;
	}
	SPFA(c,S,T,f);
	printf("%lld\n",f[T]);
}
void build(void){
	scanf("%d%d",&n,&m);
	N=n*m-1;
	S=N+1,T=N+2;
	N+=2;
	for(int i=0;i<=N;i++) c[i].clear();
	int w;
	for(int i=0;i<n;i++){
		for(int j=0;j<m-1;j++){
			scanf("%d",&w);
			if(i==0){
				if(n==1) addedge(S,T,w);
				else addedge(S,hash(i,j),w);
			}
			else if(i==n-1){
				if(n==1) addedge(S,T,w);
				else addedge(hash(i-1,j),T,w);
			}
			else addedge(hash(i-1,j),hash(i,j),w);
		}
	}
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&w);
			if(j==0){
				if(m==1) addedge(S,T,w);
				else addedge(hash(i,j),T,w);
			}
			else if(j==m-1){
				if(m==1) addedge(S,T,w);
				else addedge(S,hash(i,j-1),w);
			}
			else addedge(hash(i,j-1),hash(i,j),w);
		}
	}
}
int main(){
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		build();
		work();
	}
	return 0;
}