HDU 3870 Catch the Theves 2011 Multi-University Training Contest 4 - Host by SDU

/*第一道在平面图中 把最大流问题转换为最短路问题的题目

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=660000;
const int MAXM=1000009;
const int inf=999999999;
int n,m;
struct Edge
{
	int v,w;
	int next;
}edge[4*maxn];
int e,top;
int first[maxn];
int vis[maxn];
int Stack[maxn];
void addedge(int u,int v,int w)
{
	edge[e].v=v;edge[e].w=w;
	edge[e].next=first[u];
	first[u]=e++;
	
	edge[e].v=u;edge[e].w=w;
	edge[e].next=first[v];
	first[v]=e++;
}

int d[maxn];
int a[450][450];
void spfa()
{
	for(int i=0;i<=n*n+5;i++)
	{d[i]=inf;vis[i]=0;}
	
	d[n*n]=0;
	int front=-1,rear=-1;
	Stack[++rear]=n*n;
	while(front<rear)
	{
		int x=Stack[(++front)%maxn];
		vis[x]=0;
		for(int k=first[x];k!=-1;k=edge[k].next)
		{
		
			if(d[edge[k].v]>d[x]+edge[k].w)
			{
				d[edge[k].v]=d[x]+edge[k].w;
				if(!vis[edge[k].v])
				{
					vis[edge[k].v]=1;
					Stack[(++rear)%maxn]=edge[k].v;
				}
			}
		}
	}

	printf("%d\n",d[n*n+1]);
}
int main()
{
	int Case;
	scanf("%d",&Case);
	while(Case--)
	{
	
		memset(first,-1,sizeof(first));
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		scanf("%d",&a[i][j]);
		for(int i=0;i<n-1;i++)
		{
			addedge(n*n,i,a[0][i]);
			
			addedge(n*n,i*(n-1)+n-2,a[i][n-1]);
			
			addedge(i*(n-1),n*n+1,a[i][0]);
			
			addedge((n-2)*(n-1)+i,n*n+1,a[n-1][i]);
		}
		
		for(int i=0;i<n-1;i++)
		for(int j=0;j<n-1;j++)
		{
			if(i+1<n-1)
	
			addedge(i*(n-1)+j,(i+1)*(n-1)+j,a[i+1][j]);
	
			if(j+1<n-1)
			
			addedge(i*(n-1)+j,i*(n-1)+j+1,a[i][j+1]);
			
		}
	
		spfa();
	}
	
}