TLE最后一个点求助

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,xx;
int s,t;
long long dis[500050];
int inque[500050];
int we[550][550],ew[550][550],ns[550][550],sn[550][550];
int q[7000500],st=0,ed=0;
struct data{
	int to,nxt,val;
}mp[2200100];
int head[500050],cnt;
void link(int x,int y,int w)
{
	mp[++cnt].to=y;
	mp[cnt].nxt=head[x];
	head[x]=cnt;
	mp[cnt].val=w;
}
void spfa()
{
	memset(dis,0x3f,sizeof(dis));
	int ma=7000001;
	q[++ed]=s;inque[s]=1;
	dis[s]=0;
	int v;
	while(st!=ed)
	{
		st++;
		st%=ma;
		v=q[st];
		for(int i=head[v];i;i=mp[i].nxt)
		{
			int x=mp[i].to;
			if(dis[v]+mp[i].val<dis[x])
			{
				dis[x]=dis[v]+mp[i].val;
				if(!inque[x])
				{
					ed++;
					ed%=ma;
					q[ed]=x,inque[x]=1;
				}
			}
		}
		inque[v]=0;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n+1;++i)
		for(int j=1;j<=n;++j)scanf("%d",&we[i][j]);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n+1;++j)scanf("%d",&ns[i][j]);
	for(int i=1;i<=n+1;++i)
		for(int j=1;j<=n;++j)scanf("%d",&ew[i][j]);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n+1;++j)scanf("%d",&sn[i][j]);
	s=n*n+3;t=s+1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			xx=n*(i-1);
			if(i==1)
				link(j,t,we[i][j]),
				link(t,j,ew[j][i]);
			if(j==1)
				link(s,xx+j,ns[i][j]),
				link(xx+j,s,sn[i][j]);
			if(j==n)
				link(xx+j,t,ns[i][n+1]),
				link(t,xx+j,sn[i][n+1]);
			if(i==n)
				link(s,xx+j,we[n+1][j]),
				link(xx+j,s,ew[n+1][j]);
			if(i!=1)
				link(xx+j,n*(i-2)+j,we[i][j]);
			if(i!=n)
				link(xx+j,n*i+j,ew[i+1][j]);
			if(j!=n)
				link(xx+j,xx+j+1,ns[i][j+1]);
			if(j!=1)
				link(xx+j,xx+j-1,sn[i][j]);
		}
	spfa();
	printf("%lld\n",dis[t]);
	return 0;
}