请求增加时间

BZOJ20 sec luogu只有2 sec

我BZOJ AC了，洛谷70，怀疑被卡常，请求放宽时限。。。

#include <bits/stdc++.h>
using namespace std ;

const int N = 20010 ;
const int M = 100010 ;
const int inf = INT_MAX ;
typedef pair<int,int > pii ;

struct edge{
    int to,w,nxt ;
}e[N<<2];
struct node{
    int s1,e1,s2,e2,id ;
}q[M],p[M];//p为中转的 

int w,n,m,cnt,tot ;
int X[N],Y[N],dis[N],ans[M],head[N] ;
bool vis[N] ;

inline int id(int x,int y){return (x-1)*m+y;}
inline void add(int u,int v,int w){
    e[++cnt].w=w; 
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt ;
}
inline void dijkstra(int st,int s1,int e1,int s2,int e2){
//  cout<<st<<" "<<s1<<" "<<e1<<" "<<s2<<" "<<e2<<endl ;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for (int i=s1;i<=s2;i++)
    for (int j=e1;j<=e2;j++){
        int x=id(i,j);
        dis[x]=inf;
        vis[x]=false;
    }
    dis[st]=0;
    q.push(make_pair(0,st));
    while (!q.empty()){
        int x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=true;
        for (int i=head[x];i;i=e[i].nxt)
        if (dis[e[i].to]>dis[x]+e[i].w)
        if (X[e[i].to]>=s1&&X[e[i].to]<=s2&&Y[e[i].to]>=e1&&Y[e[i].to]<=e2) {
            dis[e[i].to]=dis[x]+e[i].w;
            q.push(make_pair(dis[e[i].to],e[i].to));
        }
    }
} 

inline void solve(int s1,int e1,int s2,int e2,int L,int R){
//  cout<<s1<<" "<<e1<<" "<<s2<<" "<<e2<<" "<<L<<" "<<R<<endl ; 
    if (L>R) return ;
    if (s2-s1>e2-e1){
        int mid=s1+s2>>1 ;
        for (int i=e1;i<=e2;i++){
            dijkstra(id(mid,i),s1,e1,s2,e2) ;
            for (int j=L;j<=R;j++){
                ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].s1,q[j].e1)]+dis[id(q[j].s2,q[j].e2)]) ;
            } 
        }
        int l=L-1,r=R+1 ;
        for (int i=L;i<=R;i++){
            if (q[i].s1<mid && q[i].s2<mid) p[++l]=q[i] ;
            else if (q[i].s1>mid && q[i].s2>mid) p[--r]=q[i] ;
        }
        for (int i=L;i<=l;i++) q[i]=p[i] ;
        for (int i=R;i>=r;i--) q[i]=p[i] ;
        solve(s1,e1,mid-1,e2,L,l); solve(mid+1,e1,s2,e2,r,R);
    }
    else {
        int mid=e1+e2>>1 ;
        for (int i=s1;i<=s2;i++){
            dijkstra(id(i,mid),s1,e1,s2,e2) ;
            for (int j=L;j<=R;j++){
                ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].s1,q[j].e1)]+dis[id(q[j].s2,q[j].e2)]) ;
            } 
        }
        int l=L-1,r=R+1 ;
        for (int i=L;i<=R;i++){
            if (q[i].e1<mid && q[i].e2<mid) p[++l]=q[i] ;
            else if (q[i].e1>mid && q[i].e2>mid) p[--r]=q[i] ;
        }
        for (int i=L;i<=l;i++) q[i]=p[i] ;
        for (int i=R;i>=r;i--) q[i]=p[i] ;
        solve(s1,e1,s2,mid-1,L,l); solve(s1,mid+1,s2,e2,r,R);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
        X[id(i,j)]=i ;
        Y[id(i,j)]=j ;
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<m;j++){
            scanf("%d",&w) ;
            int a=id(i,j),b=id(i,j+1) ;
            add(a,b,w) ;
            add(b,a,w) ; 
        }
    }
    for (int i=1;i<n;i++){
        for (int j=1;j<=m;j++){
            scanf("%d",&w) ;
            int a=id(i,j),b=id(i+1,j) ;
            add(a,b,w) ;
            add(b,a,w) ; 
        }
    } //建图完毕 
    int Q ; 
    scanf("%d",&Q) ;
    for (int i=1;i<=Q;i++){
        int s1,s2,e1,e2 ;
        scanf("%d%d%d%d",&s1,&e1,&s2,&e2) ;
        if (s1==s2 && e1==e2) ans[i]=0;
        else {
            q[++tot]=(node){s1,e1,s2,e2,i} ;
            ans[i]=inf ;
        }
    }
    solve(1,1,n,m,1,tot);
    for (int i=1;i<=Q;i++) printf("%d\n",ans[i]) ;
}