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

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const long long INF=0x7FFFFFFF;
vector <pair<int,long long> > p[11000];
long long key[11000];
bool inq[11000];
int label[101][101];
int N,M,tot;
deque <int> Q;
long long SPFA(int S,int T)
{
	for(int i=0;i<=tot;i++)key[i]=INF;
	memset(inq,false,sizeof(inq));
	key[S]=0;
	inq[S]=1;
	Q.clear();
	Q.push_back(S);
	int u,v;
	long long w;
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop_front();
		inq[u]=false;
		for(unsigned int i=0;i<p[u].size();i++)
		{
			v=p[u][i].first;
			w=p[u][i].second;
			if(w+key[u]>=key[v])continue;
			key[v]=key[u]+w;
			if(inq[v])continue;
			inq[v]=1;
			Q.push_back(v);
		}
	}
	return key[T]==INF?-1:key[T];
}
void work()
{
	memset(label,0,sizeof(label));
	scanf("%d%d",&N,&M);
	int S=0,T=1;
	long long w;
	p[0].clear();
	p[1].clear();
	for(int i=1;i<N;i++)
		label[i][0]=S;
	for(int j=1;j<M;j++)
		label[0][j]=T;
	for(int i=1;i<N;i++)
		label[i][M]=T;
	for(int j=1;j<M;j++)
		label[N][j]=S;
	tot=1;
	for(int i=1;i<N;i++)
		for(int j=1;j<M;j++)
		{
			label[i][j]=++tot;
			p[tot].clear();
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<M;j++)
		{
			scanf("%lld",&w);
			p[label[i-1][j]].push_back(make_pair(label[i][j],w));
			p[label[i][j]].push_back(make_pair(label[i-1][j],w));
		}
	for(int i=1;i<N;i++)
		for(int j=1;j<=M;j++)
		{
			scanf("%lld",&w);
			p[label[i][j-1]].push_back(make_pair(label[i][j],w));
			p[label[i][j]].push_back(make_pair(label[i][j-1],w));
		}
	printf("%lld\n",SPFA(S,T));
}
int main()
{
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		work();
	}
	return 0;
}