bzoj 3073: [Pa2011]Journeys — 线段树优化最短路
内容
3073: [Pa2011]Journeys
Time Limit: 20 Sec Memory Limit: 512 MB
Description
Seter建造了一个很大的星球，他准备建造N个国家和无数双向道路。N个国家很快建造好了，用1..N编号，但是他发现道路实在太多了，他要一条条建简直是不可能的！于是他以如下方式建造道路：(a,b),(c,d)表示，对于任意两个国家x,y，如果a<=x<=b,c<=y<=d，那么在xy之间建造一条道路。Seter保证一条道路不会修建两次，也保证不会有一个国家与自己之间有道路。Seter好不容易建好了所有道路，他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然，Seter保证P号国家能到任意一个国家。 注意：可能有重边
Input
第一行三个数N,M,P。N<=500000,M<=100000。后M行，每行4个数A，B，C，D。1<=A<=B<=N,1<=C<=D<=N。
Output
N行，第i行表示P号国家到第i个国家最少需要经过几条路。显然第P行应该是0。
Sample Input
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3
Sample Output
1
1
2
0
1
HINT
我们发现本题点数非常多，需要建的边也非常多，如果直接建图的话一定会TLE+MLE
但是我们会发现本题有一个很好的性质，就是连续一段区间都可以到达另外连续一段区间
如何优化这样连续的区间，我们就会想到一种数据结构——线段树
我们可以将线段树一段区间映射到这里，这样就可以用线段树上的几段完整表示整个区间，这也可以看成将点打包的思想
接下来我们考虑如何从【a,b】到【c,d】连边
首先，如果我们还是直接将每段线段连边的话它的复杂度还是很高
所以我们考虑抽象成新建两个点P1,P2，表示两段区间，这样从【a,b】到【c,d】，就是相当于从P1到P2连一条边
然后我们只要所有线段【a,b】向P1连边，P2向所有线段【c,d】连边就可以做到了
但是，这里还存在一个问题，就是如果把图建到一棵线段树中就会出现线段重叠，就会出问题
所以我们需要建两棵线段树A，B，表示从A会经过一条P边到B，这样就可以表示经过了一条边
然后我们对于A线段树中的点从儿子向父亲连一条权值为0的边（因为它本身属于这个集合，不需要代价）
从B线段树中的爹向儿子连一条权值为0的边（因为能到爹一定也能到儿子，不需要代价）
再从B中的叶子节点向A中对应叶子节点连一条权值为0的边（走完一条路径，到达对应点，继续从它开始出发）
这样，我们就可以跑最短路了
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define M 4000010
#define N 500010
inline int rd()
{
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 n,m,p;
int lj[M],to[M<<3],v[M<<3],fro[M<<3],cnt,ls[N<<3],rs[N<<3],ra,rb,tot,val[N],dis[M];
inline int add(int a,int b,int c){fro[++cnt]=lj[a];to[cnt]=b;v[cnt]=c;lj[a]=cnt;}
void build(int l,int r,int &x,int op)
{
x=++tot;
if(l==r){if(op) val[l]=x;return;}
int mid=l+r>>1;
build(l,mid,ls[x],op);build(mid+1,r,rs[x],op);
if(op) add(ls[x],x,0),add(rs[x],x,0);
else add(x,ls[x],0),add(x,rs[x],0);
}
void fadd(int l,int r,int x,int y)
{
if(l==r){add(y,x,0);return;}
int mid=l+r>>1;
fadd(l,mid,ls[x],ls[y]);fadd(mid+1,r,rs[x],rs[y]);
}
void padd(int l,int r,int p,int L,int R,int x,int op)
{
if(L==l&&R==r)
{
if(op) add(x,p,0);
else add(p,x,0);
return;
}
int mid=l+r>>1;
if(L>mid) padd(mid+1,r,p,L,R,rs[x],op);
else if(R<=mid) padd(l,mid,p,L,R,ls[x],op);
else
{
padd(l,mid,p,L,mid,ls[x],op);
padd(mid+1,r,p,mid+1,R,rs[x],op);
}
}
void link(int a,int b,int c,int d)
{
padd(1,n,++tot,a,b,ra,1);add(tot,tot+1,1);
padd(1,n,++tot,c,d,rb,0);
}
#define pa pair<int,int>
priority_queue<pa,vector<pa >,greater<pa > >q;
bool vs[M];
void dij()
{
memset(dis,0x3f,sizeof(dis));
int l=0,r=1,x;
dis[val[p]]=0;
q.push(make_pair(0,val[p]));
while(!q.empty())
{
x=q.top().second;q.pop();
if(vs[x]) continue;vs[x]=1;
for(int i=lj[x];i;i=fro[i])
if(dis[to[i]]>dis[x]+v[i])
{
dis[to[i]]=dis[x]+v[i];
q.push(make_pair(dis[to[i]],to[i]));
}
}
}
int main()
{
int a,b,c,d;
n=rd();m=rd();p=rd();
build(1,n,ra,1);build(1,n,rb,0);fadd(1,n,ra,rb);
for(int i=1;i<=m;i++)
{
a=rd();b=rd();c=rd();d=rd();
link(a,b,c,d);link(c,d,a,b);
}
dij();
for(int i=1;i<=n;i++) printf("%d\n",dis[val[i]]);
return 0;
}
发表评论