P6471

自己的代码没过:

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int k[2003][203];
struct node
{
    int to,lu,next;
};
node a[12000];
bool bol[4003];
int head[4003],hang[2003][203],f[4003][4003];
int cnt,n,m,x,y,z,g,ox=1,oy=1,t;
long long ans1,ans2,ans3,ans4,sum;
queue <int> q;
void make(int x,int y,int z)
{
    a[++cnt].next=head[x];
    a[cnt].to=y;
    a[cnt].lu=z;
    head[x]=cnt;
}
void spfa(int sa)
{
	int st;
    q.push(sa);
    while(!q.empty())
    {
        st=q.front();
        q.pop();
        bol[st]=0;
        for(int i=head[st];i;i=a[i].next)
        {
            if(f[sa][st]+a[i].lu<f[sa][a[i].to])
            {
                f[sa][a[i].to]=f[sa][st]+a[i].lu;
                if(!bol[a[i].to])
                {
                    bol[a[i].to]=1;
                    q.push(a[i].to);
                }
            }
        }
    }
}
int read()
{
	int sum=0;
	char c;
	c=getchar();
	if(c>='0'&&c<='9') sum=c^48;
	while((c=getchar())>='0'&&c<='9') sum=(sum<<1)+(sum<<3)+(c^48);
	return sum;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			k[i][j]=read();
			hang[i][j]=k[i][j]+hang[i][j-1];
		}
	}
	for(int i=1;i<n;i++)
	{
		x=(i<<1)-1;
		y=(i<<1);
		z=(i<<1)+1;
		g=(i+1)<<1;
		make(x,y,hang[i][m]-k[i][1]);
		make(y,x,hang[i][m]-k[i][m]);
		make(x,z,k[i+1][1]);
		make(z,x,k[i][1]);
		make(y,g,k[i+1][m]);
		make(g,y,k[i][m]);
	}
	x=(n<<1)-1;
	y=(n<<1);
	make(x,y,hang[n][m]-k[n][1]);
	make(y,x,hang[n][m]-k[n][m]);
	for(int i=1;i<=(n<<1);i++)
	{
		for(int j=1;j<=(n<<1);j++) f[i][j]=1e9;
		f[i][i]=0;
		spfa(i);
	}
	t=read();
	for(int i=1;i<=t;i++)
	{
		x=read();
		y=read();
		ans2=f[(ox<<1)-1][(x<<1)]+hang[x][m-1]-hang[x][y-1]+hang[ox][oy];
		ans3=f[(ox<<1)][(x<<1)-1]+hang[x][y]+hang[ox][m]-hang[ox][oy-1]-k[x][1];
		if(ox==x)
		{
			if(y<oy) sum+=min(min(ans3,ans2),(long long)(hang[ox][oy]-hang[x][y-1]))-k[x][y];
			else sum+=min(min(ans3,ans2),(long long)(hang[ox][y]-hang[x][oy-1]))-k[x][y];
		}
		else
		{
			ans1=f[(ox<<1)-1][(x<<1)-1]+hang[x][y]+hang[ox][oy]-k[x][1];
			ans4=f[(ox<<1)][(x<<1)]+hang[ox][m]-hang[ox][oy-1]+hang[x][m-1]-hang[x][y-1];
			sum+=min(min(ans1,ans2),min(ans3,ans4))-k[x][y];
		}
		ox=x;
		oy=y;
	}
	sum=sum+k[x][y];
	printf("%lld",sum);
}

同学的代码过了:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,c[2001][201],sum[2001][201],T,x,y,qx,qy;
ll ans;
struct node
{
    int to,lu,nxt;
};
node a[12001];
bool bol[4001];
int h[4001],f[4001][4001];
int cnt,st;
queue <int> q;
void add(int x,int y,int z)
{
    cnt++;
    a[cnt].nxt=h[x];
    a[cnt].to=y;
    a[cnt].lu=z;
    h[x]=cnt;
}
void spfa(int x)
{
    q.push(x);
    while(!q.empty())
    {
        st=q.front();
        q.pop();
        bol[st]=0;
        for(int i=h[st];i;i=a[i].nxt)
        {
            if(f[x][st]+a[i].lu<f[x][a[i].to])
            {
                f[x][a[i].to]=f[x][st]+a[i].lu;
                if(!bol[a[i].to])
                {
                    bol[a[i].to]=1;
                    q.push(a[i].to);
                }
            }
        }
    }
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=m;++j)
	    scanf("%d",&c[i][j]),sum[i][j]=sum[i][j-1]+c[i][j];
	for(int i=1;i<=2*n;++i)
	  for(int j=1;j<=2*n;++j)
	    f[i][j]=1e9;
	for(int i=1;i<=n;++i)
	{
		int x=2*i-1,y=2*i,z=2*i+1,l=2*i+2;
		if(i!=n)
		{
			add(x,z,c[i+1][1]),add(z,x,c[i][1]);
			add(y,l,c[i+1][m]),add(l,y,c[i][m]);
		}
		int s=sum[i][m];
		add(x,y,s-c[i][1]),add(y,x,s-c[i][m]);
	}
	for(int i=1;i<=2*n;++i)
	  f[i][i]=0,spfa(i);
	cin>>T;
	qx=1,qy=1;
	for(int i=1;i<=T;++i)
	{
		scanf("%d%d",&x,&y);
		ll ans1=f[2*qx-1][2*x]+sum[qx][qy]+sum[x][m-1]-sum[x][y-1];
		ll ans2=f[2*qx-1][2*x-1]+sum[x][y]-sum[x][1]+sum[qx][qy];
		ll ans3=f[2*qx][2*x-1]+sum[x][y]-sum[x][1]+sum[qx][m]-sum[qx][qy-1];
		ll ans4=f[2*qx][2*x]+sum[x][m-1]-sum[x][y-1]+sum[qx][m]-sum[qx][qy-1];
		if(x==qx)
		{
			int L=min(ans1,min(ans2,min(ans3,ans4)));
			if(y<qy)
			  ans+=min(L,sum[x][qy]-sum[x][y-1])-c[x][y];else
			  ans+=min(L,sum[x][y]-sum[x][qy-1])-c[x][y];
		}else
		ans+=min(ans1,min(ans2,min(ans3,ans4)))-c[x][y];
		qx=x,qy=y;
	}
	cout<<ans+c[x][y];
	return 0;
}