bzoj 3073 Journeys

Posted on | Views:

线段树优化连边.

  • 边是双向的.开两颗线段树, $A$ 里面节点表示一条有向边的起点,儿子向父亲连边, $B$ 里面节点表示一条有向边的终点,父亲向儿子连边, $B$ 向 $A$ 中对应的节点连边.
  • 区间连边时,新建一个节点,将区间在线段树上拆成 $log$ 个区间进行连边就好了.
  • 最后跑一次 $Dijkstra$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e5+10,MAXM=2220000;
int n,m,S;
int ecnt=0,head[MAXM],to[MAXM],nx[MAXM],val[MAXM];
void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
struct node
{
	int ls,rs;
}Tree[MAXN<<2];
#define root Tree[o]
int pos[MAXN],tot=0;
void bd1(int &o,int l,int r)
{
	o=++tot;
	if(l==r)
	{
		pos[l]=o;
		return;
	}
	int mid=(l+r)>>1;
	bd1(root.ls,l,mid);
	bd1(root.rs,mid+1,r);
	addedge(root.ls,o,0);
	addedge(root.rs,o,0);
}
void bd2(int &o,int l,int r)
{
	o=++tot;
	if(l==r)
	{
		addedge(o,pos[l],0);
		return;
	}
	int mid=(l+r)>>1;
	bd2(root.ls,l,mid);
	bd2(root.rs,mid+1,r);
	addedge(o,root.ls,0);
	addedge(o,root.rs,0);
}
void upd1(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
		addedge(o,tot,1);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		upd1(root.ls,l,mid,L,R);
	if(R>mid)
		upd1(root.rs,mid+1,r,L,R);
}
void upd2(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
		addedge(tot,o,1);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		upd2(root.ls,l,mid,L,R);
	if(R>mid)
		upd2(root.rs,mid+1,r,L,R);
}
int rt1=0,rt2=0;
int vis[MAXM],dis[MAXM];
typedef pair<int,int> pii;
#define mp make_pair
priority_queue<pii> q;
void Dijkstra()
{
	memset(dis,0x7f,sizeof dis);
	dis[pos[S]]=0;
	q.push(mp(0,pos[S]));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(dis[v]-dis[u]>val[i])
			{
				dis[v]=dis[u]+val[i];
				q.push(mp(-dis[v],v));
			}
		}
	}
}
int main()
{
	n=read(),m=read(),S=read();
	bd1(rt1,1,n);
	bd2(rt2,1,n);
	while(m--)
	{
		int x1=read(),y1=read(),x2=read(),y2=read();
		++tot;upd1(rt1,1,n,x1,y1);upd2(rt2,1,n,x2,y2);
		++tot;upd1(rt1,1,n,x2,y2);upd2(rt2,1,n,x1,y1);
	}
	Dijkstra();
	for(int i=1;i<=n;++i)
		printf("%d\n",dis[pos[i]]>>1);
	return 0;
}