题解

#include<bits/stdc++.h>

#define rep(i,a,b) for( int i(a); i <= b; ++i)
#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 1e18
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define PI acos(-1)
#define fi first
#define se second
#define pb push_back
#define debug(x) printf("x=%d\n",x);
#define ls(x) treap[x].child[0]
#define rs(x) treap[x].child[1]
#define INF 0x3f3f3f3f
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)

using namespace std;

constexpr int MAXN=2e5+10;
const int N=2e5+7;
const int M=2e5+5;
const ll mod=1e9+7;
double eps=1e-8;
inline int read()
{
ll X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int a[2002][202],psum[2002][202],n,m;

struct EDGE
{
int v,w,nxt;
}ed[13171];
int head[4011],ecnt=0;
ll dis[4011][4011];
bool vis[4011];
void add(int u,int v,int w)
{
ed[ecnt].v=v; ed[ecnt].w=w; ed[ecnt].nxt=head[u]; head[u]=ecnt++;
}
void dij(int s)//spfa
{
deque<int>q;
rep(i,0,n) dis[s][i]=dis[s][i+n]=1e15;
memset(vis,0,sizeof(vis));
dis[s][s]=0; vis[s]=1;
q.push_back(s);
while(!q.empty())
{
auto u=q.front(); q.pop_front();
vis[u]=0;
for(int i=head[u];~i;i=ed[i].nxt)
{
int v=ed[i].v,w=ed[i].w;
if(dis[s][v]>dis[s][u]+w)
{
dis[s][v]=dis[s][u]+w;
if(!vis[v])
{
if(!q.empty()&&dis[s][v]>dis[s][q.front()])
q.push_back(v);
else q.push_front(v);
vis[v]=1;
}
}
}
}
}
void init()
{

rep(i,1,n)
{
    add(i,i+n,psum[i][m]-a[i][1]);
    add(i+n,i,psum[i][m-1]);
    if(i!=1) add(i,i-1,a[i-1][1]),add(i+n,i+n-1,a[i-1][m]);
    if(i!=n) add(i,i+1,a[i+1][1]),add(i+n,i+n+1,a[i+1][m]);
}
rep(i,1,n) dij(i),dij(i+n);

}
int go(int x,int y,int yy)
{
if(yy>y) return psum[x][yy]-psum[x][y];
else if(yy<y) return psum[x][y-1]-psum[x][yy-1];
else return 0;
}

void solvve()
{
memset(psum,0,sizeof(psum));
memset(head,-1,sizeof(head));
gbtb;
cin>>n>>m;
// n=read(),m=read();
rep(i,1,n) rep(j,1,m) cin>>a[i][j],psum[i][j]=psum[i][j-1]+a[i][j];
init();
// debug(getmin(2,n,1))
int q;
cin>>q;
ll ans=a[1][1];
int lastx=1,lasty=1;
while(q--)
{
int nowx,nowy;
cin>>nowx>>nowy;
ll res=1e18;
if(nowx==lastx) res=min(res,1ll*go(nowx,lasty,nowy));
// if(nowx!=lastx)
res=min(res,dis[lastx][nowx]+go(lastx,lasty,1)+go(nowx,1,nowy));
res=min(res,dis[lastx+n][nowx]+go(lastx,lasty,m)+go(nowx,1,nowy));
res=min(res,dis[lastx][nowx+n]+go(lastx,lasty,1)+go(nowx,m,nowy));
// if(nowx!=lastx)
res=min(res,dis[lastx+n][nowx+n]+go(lastx,lasty,m)+go(nowx,m,nowy));
ans+=res;
// debug(res)
lastx=nowx,lasty=nowy;
}
cout<<ans<<'\n';
}
int main()
{

// int _=read();while(_--) 
    solvve();

return 0;

}