Bzoj4456 [Zjoi2016]旅行者

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 429 Solved: 264

Description

小Y来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有n条从东到西的道路和m条从南到北

的道路，这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m)。她发现不同的道路路况不同，所以通过不

同的路口需要不同的时间。通过调查发现，从路口(i,j)到路口(i,j+1)需要时间 r(i,j)，从路口(i,j)到路口(i+1

,j)需要时间c(i,j)。注意这里的道路是双向的。小Y有q个询问，她想知道从路口(x1,y1)到路口(x2,y2)最少需要

花多少时间。

Input

第一行包含 2 个正整数n,m，表示城市的大小。

接下来n行，每行包含m?1个整数，第i行第j个正整数表示从一个路口到另一个路口的时间r(i,j)。

接下来n?1行，每行包含m个整数，第i行第j个正整数表示从一个路口到另一个路口的时间c(i,j)。

接下来一行，包含1个正整数q，表示小Y的询问个数。

接下来q行，每行包含4个正整数 x1,y1,x2,y2，表示两个路口的位置。

Output

输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

Sample Input

2 2
2
3
6 4
2
1 1 2 2
1 2 2 1

Sample Output

6
7

HINT

题解:JudgeOnline/upload/201603/4456 sol.txt

Source

图论分治最短路

本质上是个分治最短路，但是卡常丧心病狂啊……

询问辣么多，当然不资瓷挨个算最短路。

注意到给定的图是一个矩形，十分适合分治。

找到矩形较长的那条边的中垂线，以这条线上的每一点为源跑dijkstra，回答询问。然后把起终点都在左边的询问和都在右边的询问分开，递归处理两边的矩形。

很简单对吧

写起来也不复杂

但是卡常丧心病狂？

UOJ上卡在50分，Bzoj 21s AC (时限20s，exm?)，status排在倒rank2 (居然还有一个比我慢4ms的)

然后乱搞一个小时各种卡常数。

有效的大概有这些：

算点编号的时候，把第9行的define换成第37行的register 21s -> 20s (-1s)；

发现calc里枚举的起点范围好像超出了分治范围，改掉；

加了第57行的防出界；

第93行划分询问的时候把for i = ql to qr拆成ql to L 和 R to qr；

学了heheda的写法，dij里面加了个vis函数；

每次求最短路的时候不把dis重置到INF，而是加上新源到旧源的距离；

于是成功在UOJ上AC，在Bzoj卡到榜第二页

感人至深

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<map>
  7 #include<vector>
  8 #include<queue>
  9 //#define id(x,y) ((x)-1)*m+(y)
 10 using namespace std;
 11 const int INF=1<<29;
 12 const int mxn=30011;
 13 int read(){
 14     int x=0,f=1;char ch=getchar();
 15     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 16     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 17     return x*f;
 18 }
 19 struct edge{
 20     int v,nxt,w;
 21 }e[mxn<<4];
 22 int hd[mxn],mct=0;
 23 inline void add_edge(int u,int v,int w){
 24     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return;
 25 }
 26 inline void addedge(int u,int v,int w){
 27     add_edge(u,v,w);add_edge(v,u,w);return;
 28 }
 29 struct node{
 30     int u,dis;
 31     node(int a,int b){u=a;dis=b;}
 32     bool operator < (const node &b)const{
 33         return dis>b.dis;
 34     }
 35 };
 36 int n,m;
 37 inline int id(register int a,register int b){return (a-1)*m+b;}
 38 int dis[mxn];
 39 bool vis[mxn];
 40 int idx[mxn],idy[mxn];
 41 priority_queue<node>q;
 42 void Dij(int S,int x1,int y1,int x2,int y2,int w){
 43     for(int i=x1;i<=x2;i++)
 44         for(int j=y1;j<=y2;j++){
 45             int t=id(i,j);
 46             (w<0)?dis[t]=INF:dis[t]+=w;
 47             vis[t]=0;
 48         }
 49     q.push(node(S,0));dis[S]=0;
 50     while(!q.empty()){
 51         node U=q.top();q.pop();
 52         if(U.dis>dis[U.u])continue;
 53         int u=U.u,v;
 54         if(vis[u])continue;vis[u]=1;
 55         for(int i=hd[u];i;i=e[i].nxt){
 56             v=e[i].v;
 57             if(idx[v]<x1 || idx[v]>x2 || idy[v]<y1 || idy[v]>y2)continue;
 58             if(dis[v]>dis[u]+e[i].w){
 59                 dis[v]=dis[u]+e[i].w;
 60                 q.push(node(v,dis[v]));
 61             }
 62         }
 63     }
 64     return;
 65 }
 66 //
 67 struct Que{
 68     int x1,y1,x2,y2;
 69     int x,y;
 70     int id;
 71 }Q[mxn*5];
 72 int qid[mxn*5],ans[mxn*5];
 73 int b[mxn*5];
 74 int Qt;//总询问数 
 75 //
 76 void calc(int x1,int x2,int y1,int y2,int ql,int qr){
 77     if(ql>qr || x1>x2 || y1>y2)return;
 78     if(x2-x1<=y2-y1){//与较短的一边平行拆分 
 79         int mid=(y1+y2)>>1;
 80         int L=ql-1,R=qr+1;
 81         for(int i=ql,t;i<=qr;i++){
 82             t=qid[i];
 83             if(Q[t].y1<mid && Q[t].y2<mid)b[++L]=t;
 84             else if(Q[t].y1>mid && Q[t].y2>mid)b[--R]=t;
 85         }
 86         dis[id(x1,mid)]=-1;
 87         for(int i=x1;i<=x2;i++){
 88             int u=id(i,mid);
 89             Dij(u,x1,y1,x2,y2,dis[u]);
 90             for(int j=ql;j<=qr;j++)
 91                 ans[Q[qid[j]].id]=min(ans[Q[qid[j]].id],dis[id(Q[qid[j]].x1,Q[qid[j]].y1)]+dis[id(Q[qid[j]].x2,Q[qid[j]].y2)]);
 92         }
 93         for(int i=ql;i<=L;i++)qid[i]=b[i];
 94         for(int i=R;i<=qr;i++)qid[i]=b[i];
 95         calc(x1,x2,y1,mid-1,ql,L);
 96         calc(x1,x2,mid+1,y2,R,qr);
 97     }
 98     else{
 99         int mid=(x1+x2)>>1;
100         int L=ql-1,R=qr+1;
101         for(int i=ql,t;i<=qr;i++){
102             t=qid[i];
103             if(Q[t].x1<mid && Q[t].x2<mid)b[++L]=t;
104             else if(Q[t].x1>mid && Q[t].x2>mid)b[--R]=t;
105         }
106         dis[id(mid,y1)]=-1;
107         for(int i=y1;i<=y2;i++){
108             int u=id(mid,i);
109             Dij(u,x1,y1,x2,y2,dis[u]);
110             for(int j=ql;j<=qr;j++)
111                 ans[Q[qid[j]].id]=min(ans[Q[qid[j]].id],dis[Q[qid[j]].x]+dis[Q[qid[j]].y]);
112         }
113         for(int i=ql;i<=L;i++)qid[i]=b[i];
114         for(int i=R;i<=qr;i++)qid[i]=b[i];
115         calc(x1,mid-1,y1,y2,ql,L);
116         calc(mid+1,x2,y1,y2,R,qr);
117     }
118     return;
119 }
120 int main(){
121     int i,j,w;
122     n=read();m=read();
123     for(i=1;i<=n;i++)
124         for(j=1;j<m;j++)
125             w=read(),addedge(id(i,j),id(i,j+1),w);
126     for(i=1;i<n;i++)
127         for(j=1;j<=m;j++)
128             w=read(),addedge(id(i,j),id(i+1,j),w);
129     for(i=1;i<=n;i++)
130         for(j=1;j<=m;j++){
131             int t=id(i,j);idx[t]=i;idy[t]=j;
132         }
133     Qt=read();
134     for(i=1;i<=Qt;i++){
135         Q[i].x1=read();Q[i].y1=read();
136         Q[i].x2=read();Q[i].y2=read();
137         Q[i].x=id(Q[i].x1,Q[i].y1);
138         Q[i].y=id(Q[i].x2,Q[i].y2);
139         Q[i].id=i;
140         qid[i]=i;
141         ans[i]=INF;
142     }
143     calc(1,n,1,m,1,Qt);
144     for(i=1;i<=Qt;i++){
145         printf("%d
",ans[i]);
146     }
147     return 0;
148 }