首页 > 代码库 > 【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra

【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra

题目描述

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号国家能到任意一个国家。
注意:可能有重边

输入

第一行三个数N,M,P。N<=500000,M<=100000。
后M行,每行4个数A,B,C,D。1<=A<=B<=N,1<=C<=D<=N。

输出

N行,第i行表示P号国家到第i个国家最少需要经过几条路。显然第P行应该是0。

样例输入

5 3 4
1 2 4 5
5 5 4 4
1 1 3 3

样例输出

1
1
2
0
1


题解

线段树优化建图+堆优化Dijkstra

看别人blog看到了这道题,于是决定YY一发。

一个朴素(已经不是最朴素的了)的加边方法:a~b的所有点->p1,长度为0;p1->p2,长度为1;p2->c~d的所有点,长度为0,其中加的都是有向边,p1和p2是新建的两个辅助点,然后再反过来进行这个过程。

然而这样加边的话边数依旧巨大。

由于给出的加边都是区间形式,所以我们可以用维护区间的数据结构——线段树,去优化这个建图过程。

具体方法(这里只讲加有向边a~b->c~d的方法):

建立两颗线段树A、B,其中A线段树每个非叶子节点的儿子向该节点连边,长度为0,B线段树每个非叶子节点向该节点的儿子连边,长度为0;B线段树的叶子结点向A线段树对应的叶子结点连边,长度为0。

这里面A线段树的叶子结点代表原图中的节点,其余节点都是用来优化建图。

对于加边操作,找到A线段树上a~b对应的区间节点,这些节点向p1连边,长度为0;p1->p2,长度为1;找到B线段树上c~d对应的区间节点,p2向这些节点连边,长度为0.

最后跑堆优化Dijkstra出解。

应该不是很难理解,具体可以见代码。

#include <cstdio>#include <cstring>#include <queue>#include <utility>#define N 500010#define M 3500010using namespace std;priority_queue<pair<int , int> > q;int head[M] , to[M << 3] , len[M << 3] , next[M << 3] , cnt , ls[N << 3] , rs[N << 3] , ra , rb , tot , v[N] , n , dis[M] , vis[M];void add(int x , int y , int z){	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}void build(int l , int r , int &x , int flag){	x = ++tot;	if(l == r)	{		if(flag) v[l] = x; 		return;	}	int mid = (l + r) >> 1;	build(l , mid , ls[x] , flag) , build(mid + 1 , r , rs[x] , flag);	if(flag) add(ls[x] , x , 0) , add(rs[x] , x , 0);	else add(x , ls[x] , 0) , add(x , rs[x] , 0);}void deal(int l , int r , int x , int y){	if(l == r)	{		add(y , x , 0);		return;	}	int mid = (l + r) >> 1;	deal(l , mid , ls[x] , ls[y]) , deal(mid + 1 , r , rs[x] , rs[y]);}void update(int b , int e , int p , int l , int r , int x , int flag){	if(b <= l && r <= e)	{		if(flag) add(x , p , 0);		else add(p , x , 0);		return;	}	int mid = (l + r) >> 1;	if(b <= mid) update(b , e , p , l , mid , ls[x] , flag);	if(e > mid) update(b , e , p , mid + 1 , r , rs[x] , flag);}void link(int a , int b , int c , int d){	update(a , b , ++tot , 1 , n , ra , 1) , add(tot , tot + 1 , 1) , update(c , d , ++tot , 1 , n , rb , 0);}int main(){	int m , p , a , b , c , d , i , x;	scanf("%d%d%d" , &n , &m , &p);	build(1 , n , ra , 1) , build(1 , n , rb , 0) , deal(1 , n , ra , rb);	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d" , &a , &b , &c , &d) , link(a , b , c , d) , link(c , d , a , b);	memset(dis , 0x3f , sizeof(dis)) , dis[v[p]] = 0 , q.push(make_pair(0 , v[p]));	while(!q.empty())	{		x = q.top().second , q.pop();		if(vis[x]) continue;		vis[x] = 1;		for(i = head[x] ; i ; i = next[i])			if(dis[to[i]] > dis[x] + len[i])				dis[to[i]] = dis[x] + len[i] , q.push(make_pair(-dis[to[i]] , to[i]));	}	for(i = 1 ; i <= n ; i ++ ) printf("%d\n" , dis[v[i]]);	return 0;}

 

 

【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra