\(Description\)
给你一张\(n\times m\)的网格图及每条边边权，有\(q\)组询问，每次询问两点间的最短距离。
\(Solution\)
暴力做法是枚举所有询问点跑最短路，复杂度\(O(qnlogn)\)，由于\(q\)很大，过不了这个题 考虑分治，每次找到一条分界线，如果询问两点都在左边或者都在右边，递归处理即可，当点在两边，以分界线上每个点为起点跑最短路，扫一遍不停更新即可。 显然我们的时间复杂度取决于分界线的长度，因此我们对于每个矩形，垂直于长边切即可，也就是让它趋近于长方形这篇博客证明时间复杂度为\(O(S\sqrt SlogS)\)
\(Code\)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define re register
#define maxn 200010
#define inf 0x3f3f3f3f
#define id(i,j) ((i-1)*m+(j))
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int head[maxn],ans[maxn],cnt,dis[maxn],num;
int n,m,Q,invx[maxn] ,invy[maxn],vis[maxn];
struct Query{
int x,y,xx,yy,id;
}q[maxn],tmp[maxn];
struct Edge{
int v,nxt,w;
}e[maxn<<2];
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
e[++cnt].v=u;
e[cnt].w=w;
e[cnt].nxt=head[v];
head[v]=cnt;
}
struct node{
int u,d;
bool operator <(const node&rhs) const{
return d>rhs.d;
}
};
void dijkstra(int s,int xl,int xr,int yl,int yr,int h)
{
int d=dis[s];
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue<node> qq;
qq.push(node{s,0});
while(!qq.empty())
{
node f=qq.top();
qq.pop();
int now=f.u;
if(vis[now])
continue;
vis[now]=1;
for(int i=head[now];i;i=e[i].nxt)
{
int ev=e[i].v;
if(invx[ev]>=xl&&invx[ev]<=xr&&invy[ev]>=yl&&invy[ev]<=yr)
{
if(dis[ev]>dis[now]+e[i].w)
{
dis[ev]=dis[now]+e[i].w;
if(!vis[ev])
{
qq.push((node){ev,dis[ev]});
}
}
}
}
}
}
void work(int xl,int xr,int yl,int yr,int ql,int qr)
{
if(ql>qr) return;
if(xr-xl>yr-yl)//判断哪条边长
{
int mid=(xl+xr)>>1;
for(int i=yl;i<=yr;++i)
{
dijkstra(id(mid,i),xl,xr,yl,yr,i-yl);//对范围内点跑最短路
//如果在分界线两侧则更新完成，否则还不是最优解，继续递归
// for(re int j=1;j<=num;++j)
// {
// printf("now:%d %d dis:%d\n",invx[j],invy[j],dis[j]);
// }
for(re int j=ql;j<=qr;++j)
ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x,q[j].y)]+dis[id(q[j].xx,q[j].yy)]);
}
int l=ql-1,r=qr+1;
for(int i=ql;i<=qr;++i)
{
if(q[i].x<mid&&q[i].xx<mid)
tmp[++l]=q[i];
else if(q[i].x>mid&&q[i].xx>mid)
tmp[--r]=q[i];
}
for(int i=ql;i<=l;++i)
q[i]=tmp[i];
for(int i=r;i<=qr;++i)
q[i]=tmp[i];
work(xl,mid-1,yl,yr,ql,l);
work(mid+1,xr,yl,yr,r,qr);
}
else
{
int mid=(yl+yr)>>1;
for(int i=xl;i<=xr;++i)
{
dijkstra(id(i,mid),xl,xr,yl,yr,i-xl);
// for(re int j=1;j<=num;++j)
// {
// printf("now:%d %d dis:%d\n",invx[j],invy[j],dis[j]);
// }
for(re int j=ql;j<=qr;++j)
ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x,q[j].y)]+dis[id(q[j].xx,q[j].yy)]);
}
int l=ql-1,r=qr+1;
for(int i=ql;i<=qr;++i)
{
if(q[i].y<mid&&q[i].yy<mid)
tmp[++l]=q[i];
else if(q[i].y>mid&&q[i].yy>mid)
tmp[--r]=q[i];
}
for(int i=ql;i<=l;++i)
q[i]=tmp[i];
for(int i=r;i<=qr;++i)
q[i]=tmp[i];
work(xl,xr,yl,mid-1,ql,l);
work(xl,xr,mid+1,yr,r,qr);
}
}
int main()
{
memset(ans,0x7f,sizeof(ans));
n=read(),m=read();
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j)
{
invx[++num]=i;
invy[num]=j;
}
for(re int i=1;i<=n;++i)
for(re int j=1;j<m;++j)
{
add(id(i,j),id(i,j+1),read());//将二维转为一维
}
for(re int i=1;i<n;++i)
for(re int j=1;j<=m;++j)
{
add(id(i,j),id(i+1,j),read());
}
Q=read();
for(re int i=1;i<=Q;++i)
{
q[i].x=read(),q[i].y=read(),q[i].xx=read(),q[i].yy=read();
q[i].id=i;
}
// for(re int i=1;i<=num;++i)
// {
// printf("u:%d %d\n",invx[i],invy[i]);
// for(re int j=head[i];j;j=e[j].nxt)
// {
// printf("v:%d %d w:%d\n",invx[e[j].v],invy[e[j].v],e[j].w);
// }
// }
work(1,n,1,m,1,Q);
for(re int i=1;i<=Q;++i)
printf("%d\n",ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/Liuz8848/p/11285384.html
相关资源：JAVA上百实例源码以及开源项目
