BDF1 @ 2017-02-09 11:55:34
···cpp
#include<ext/pb_ds/priority_queue.hpp>
#include<cstdio>
#include<cstring>
using namespace std;
struct lzqhkf{
int x,y;long long w;
lzqhkf(int a,int b,long long d):x(a),y(b),w(d){};
lzqhkf(){x=y=w=0;}
bool operator<(lzqhkf hkf)const{
return w>hkf.w;
}
};
struct clc{
int x,y,X,Y,id;
};
clc A[102400],B[102400];
typedef __gnu_pbds::priority_queue<lzqhkf>heap;
heap a;
bool*in[100007];
heap::point_iterator*id[100007];
int T[4]={-1,1,0,0},Z[4]={0,0,-1,1},n,m,x,y,xx,yy,Q;
int*dis[100007];int ans[100007];
int*c[4][100007];
void di(int x_,int y_,int x,int X,int y,int Y){
a.clear();
for(int i=x-1;i<=X+1;i++)for(int j=y-1;j<=Y+1;j++)dis[i][j]=1073741823,in[i][j]=0;
in[x_][y_]=1;dis[x_][y_]=0;
id[x_][y_]=a.push(lzqhkf(x_,y_,0));
while(!a.empty()){
lzqhkf st=a.top();a.pop();
int _x=st.x,_y=st.y;int w=st.w;
//printf("now %d %d\n",_x,_y);
for(int k=0;k<4;k++){
int xx=_x+T[k],yy=_y+Z[k];
//printf("xx=%d yy=%d x=%d y=%d X=%d Y=%d\n",xx,yy,x,y,X,Y);
if(xx<x||xx>X||yy<y||yy>Y)continue;
if(w+c[k][_x][_y]<dis[xx][yy]){
dis[xx][yy]=w+c[k][_x][_y];
//printf("%d %d %d\n",xx,yy,dis[xx][yy]);
if(in[xx][yy])a.modify(id[xx][yy],lzqhkf(xx,yy,dis[xx][yy]));
else in[xx][yy]=1,id[xx][yy]=a.push(lzqhkf(xx,yy,dis[xx][yy]));
}//else printf("%d %d:%d\n",w,c[k][x][y],dis[xx][yy]);
}
}
}
void sol(int x,int X,int y,int Y,int q,int Q){
if(q>Q)return;
if(X-x>Y-y){
int m=x+X>>1;
for(int i=y;i<=Y;i++){
di(m,i,x,X,y,Y);
//printf("(%d %d) (%d %d) (%d %d)\n",x,y,X,Y,m,i);
//for(int i=x;i<=X;i++,puts(""))for(int j=y;j<=Y;j++)printf("%d ",dis[i][j]);
for(int j=q;j<=Q;j++)if(ans[A[j].id]>dis[A[j].x][A[j].y]+dis[A[j].X][A[j].Y])
ans[A[j].id]=dis[A[j].x][A[j].y]+dis[A[j].X][A[j].Y];
}
int j=q,k=Q;
for(int i=q;i<=Q;i++)if(A[i].x<m&&A[i].X<m)B[j++]=A[i];
else if(A[i].x>m&&A[i].X>m)B[k--]=A[i];
for(int i=q;i<j;i++)A[i]=B[i];for(int i=Q;i>k;i--)A[i]=B[i];
sol(x,m-1,y,Y,q,j-1),sol(m+1,X,y,Y,k+1,Q);
}
else{
int m=y+Y>>1;
for(int i=x;i<=X;i++){
di(i,m,x,X,y,Y);
//printf("(%d %d) (%d %d) (%d %d)\n",x,y,X,Y,i,m);
//for(int i=x;i<=X;i++,puts(""))for(int j=y;j<=Y;j++)printf("%d ",dis[i][j]);
for(int j=q;j<=Q;j++)if(ans[A[j].id]>dis[A[j].x][A[j].y]+dis[A[j].X][A[j].Y])
ans[A[j].id]=dis[A[j].x][A[j].y]+dis[A[j].X][A[j].Y];
}
int j=q,k=Q;
for(int i=q;i<=Q;i++)if(A[i].y<m&&A[i].Y<m)B[j++]=A[i];
else if(A[i].y>m&&A[i].Y>m)B[k--]=A[i];
for(int i=q;i<j;i++)A[i]=B[i];for(int i=Q;i>k;i--)A[i]=B[i];
sol(x,X,y,m-1,q,j-1),sol(x,X,m+1,Y,k+1,Q);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int I=0;I<4;I++)for(int i=0;i<=n+1;i++)c[I][i]=new int[m+2];
for(int i=0;i<=n+1;i++)dis[i]=new int[m+2],in[i]=new bool[m+2],id[i]=new heap::point_iterator[m+2];
for(int i=1;i<=n;i++)for(int j=1;j<m;j++)scanf("%d",&c[3][i][j]),c[2][i][j+1]=c[3][i][j];
for(int i=1;i<n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[1][i][j]),c[0][i+1][j]=c[1][i][j];
scanf("%d",&Q);
//for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("(%d %d %d %d\n)")
for(int i=1;i<=Q;i++){
int x,y,X,Y;scanf("%d%d%d%d",&x,&y,&X,&Y);
A[i]=(clc){x,y,X,Y,i};ans[i]=1e9+7;
}sol(1,n,1,m,1,Q);
for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
}
···by kkksc03 @ 2017-02-11 02:48:19
@BDF1 已经加大时限
by system_has_collapsed @ 2018-02-09 16:52:39
#include<bits/stdc++.h>
template<typename T> inline void read(T& a)
{
T x = 0,f = 1;
char ch = getchar();
while((ch < '0') or (ch > '9'))
{
if(ch == '-' )
f = -1;
ch = getchar();
}
while((ch >= '0') and (ch <= '9'))
{
x = x * 10 + ch - '0';
ch = getchar();
}
a = x * f;
}
using namespace std;
inline void readl()
{
char ch;
ch = getchar();
while(ch != '\n')
ch = getchar();
}
int dis[200005],dis2[200005],tp[200005],f[200005],v[200005],i,j,k,n,m,cnt,w[100005];
int r[200005],c[200005],q[100005][5],a[100005],qq,ans[100005];
const int fx[4] = {-1,0,1,0};
const int fy[4] = {0,-1,0,1};
inline void up(int x)
{
int t,i;
while(x > 1)
{
i = x / 2;
if(dis[tp[x]] < dis[tp[i]])
{
swap(tp[i],tp[x]);
w[tp[x]] = x;
w[tp[i]] = i;
x = i;
}
else
break;
}
}
inline void down(int x)
{
int t,i,j;
while (true)
{
i = x * 2;
j = i + 1;
if((j <= cnt) and (dis[tp[j]] < dis[tp[i]]))
i = j;
if((i <= cnt) and (dis[tp[i]] < dis[tp[x]]))
{
swap(tp[x],tp[i]);
w[tp[x]] = x;
w[tp[i]] = i;
x = i;
}
else
break;
}
}
inline void dij(int x,int y,int ll1,int rr1,int ll2,int rr2)
{
cnt = 0;
int k,xx,yy,xxx,yyy,disk,mu,jia,tot = 0;
int i,j;
for(i = ll1;i <= rr1;i++)
for(j = ll2;j <= rr2;j++)
{
tot++;
mu = m * (i - 1) + j - 1;
v[mu] = 0;
if((i == x) and (j == y))
dis[mu] = 0,cnt++,tp[cnt] = mu,w[mu] = cnt,up(cnt);
else
dis[mu] = 1000000000;
}
for(i = 1;i <= tot;i++)
{
k = tp[1];
v[k] = 1;
disk = dis[k];
dis2[k] = dis[k];
dis[k] = 2000000000;
down(1);
xx = k / m + 1;
yy = k % m + 1;
for(j = 0;j <= 3;j++)
if((xx + fx[j] >= ll1) and (xx + fx[j] <= rr1) and (yy + fy[j] >= ll2) and (yy + fy[j] <= rr2))
{
xxx = xx + fx[j];
yyy = yy +fy[j];
mu = m *(xxx - 1) + yyy - 1;
if(v[mu] == 1)
continue;
if(j == 0)
jia = c[mu];
else if (j == 1)
jia=r[mu];
else
if(j == 2)
jia = c[mu - m];
else
jia = r[mu - 1];
if(disk + jia < dis[mu])
{
if(dis[mu] == 1000000000)
cnt++,tp[cnt] = mu,w[mu] = cnt;
dis[mu] = disk + jia;
up(w[mu]);
}
}
}
}
inline bool in(int x,int l1,int r1,int l2,int r2)
{
return ((q[x][1] >= l1) and (q[x][1] <= r1) and (q[x][2] >= l2) and (q[x][2] <= r2) and (q[x][3] >= l1) and (q[x][3] <= r1) and (q[x][4] >= l2) and (q[x][4] <= r2));
}
void ss(int l1,int r1,int l2,int r2,int ql,int qr)
{
if((l1 > r1) or (l2 > r2) or (ql > qr))
return;
int i = ql,j = qr,l3 = l1,r3 = r1,l4 = l2,r4 = r2,l5 = l1,r5 = r1,l6 = l2,r6 = r2,x,midx,t,ii,jj;
if((r2 - l2 > r1 - l1))
{
x = 2;
midx = (r2 + l2) / 2;
r4 = midx - 1;
l6 = midx + 1;
}
else
{
x = 1;
midx = (r1 + l1) / 2;
r3 = midx - 1;
l5 = midx + 1;
}
while(i <= j)
{
while((i <= qr) and ((in(a[i],l3,r3,l4,r4)) or (in(a[i],l5,r5,l6,r6))))
i++;
while((j >= ql) and (not ((in(a[j],l3,r3,l4,r4)) or (in(a[j],l5,r5,l6,r6)))))
j--;
if (i <= j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(x == 1)
{
for(ii = l2;ii <= r2;ii++)
{
dij(midx,ii,l1,r1,l2,r2);
for(jj = ql;jj <= qr;jj++)
ans[a[jj]] = min(ans[a[jj]],dis2[m * (q[a[jj]][1] - 1) + q[a[jj]][2] - 1] + dis2[m * (q[a[jj]][3] - 1) + q[a[jj]][4] - 1]);
}
}
else
{
for(ii = l1;ii <= r1;ii++)
{
dij(ii,midx,l1,r1,l2,r2);
for(jj = ql;jj <= qr;jj++)
ans[a[jj]] = min(ans[a[jj]],dis2[m * (q[a[jj]][1] - 1) + q[a[jj]][2] - 1] + dis2[m * (q[a[jj]][3] - 1) + q[a[jj]][4] - 1]);
}
}
qr = i - 1;
if(ql > qr)
return;
i = ql;
j = qr;
while(i <= j)
{
while((i <= qr) and (in(a[i],l3,r3,l4,r4)))
i++;
while((j >= ql) and (in(a[j],l5,r5,l6,r6)))
j--;
if(i <= j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(i <= qr)
ss(l5,r5,l6,r6,i,qr);
if(j <= ql)
ss(l3,r3,l4,r4,ql,j);
}
int main()
{
cin >> n;
cin >> m;
for(i = 1;i <= n;i++)
for(j = 1;j <= m - 1;j++)
cin >> r[m * (i - 1) + j - 1];
for(i = 1;i <= n - 1;i++)
for(j = 1;j <= m;j++)
cin >> c[m * (i - 1) + j - 1];
cin >> qq;
for(i = 1;i <= qq;i++)
{
cin >> q[i][1];
cin >> q[i][2];
cin >> q[i][3];
cin >> q[i][4];
a[i] = i;
ans[i] = 2000000000;
}
ss(1,n,1,m,1,qq);
for(i = 1;i <= qq;i++)
cout << ans[i] << endl;//printf("%d\n",ans[i]);
}麻烦看一下有什么错误