3073: [Pa2011]Journeys
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 243 Solved: 80
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 41 2 4 55 5 4 41 1 3 3
Sample Output
11201
区间建边
线段树优化最短路,高级吧
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
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<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
const int N=3000000;
int n,m,p,ecnt,last[3000005],pos[500005],dis[3000005],sz;
bool book[3000005];
struct EDGE{int to,nt,val;}e[30000005];
inline void add(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
struct segtree{int pos;}tr1[2500005],tr2[2500005];
void build1(int k,int l,int r)
{
tr1[k].pos=++sz;
if(l==r){pos[l]=sz;return ;}
int mid=l+r>>1;
build1(k<<1,l,mid);build1(k<<1|1,mid+1,r);
add(tr1[k<<1].pos,tr1[k].pos,0);add(tr1[k<<1|1].pos,tr1[k].pos,0);
}
void build2(int k,int l,int r)
{
tr2[k].pos=++sz;add(tr2[k].pos,tr1[k].pos,0);
if(l==r)return ;
int mid=l+r>>1;
build2(k<<1,l,mid);build2(k<<1|1,mid+1,r);
add(tr2[k].pos,tr2[k<<1].pos,0);add(tr2[k].pos,tr2[k<<1|1].pos,0);
}
void insert1(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
{add(tr1[k].pos,sz,1);return;}
int mid=l+r>>1;
if(mid<x)insert1(k<<1|1,mid+1,r,x,y);
else if(y<=mid)insert1(k<<1,l,mid,x,y);
else insert1(k<<1,l,mid,x,y),insert1(k<<1|1,mid+1,r,x,y);
}
void insert2(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
{add(sz,tr2[k].pos,1);return;}
int mid=l+r>>1;
if(mid<x)insert2(k<<1|1,mid+1,r,x,y);
else if(y<=mid)insert2(k<<1,l,mid,x,y);
else insert2(k<<1,l,mid,x,y),insert2(k<<1|1,mid+1,r,x,y);
}
struct cmp
{
bool operator()(int a,int b)
{return dis[a]>dis[b];}
};
priority_queue<int,vector<int>,cmp>q;
void dijkstra()
{
memset(dis,0X3f,sizeof(dis));
q.push(pos[p]);book[pos[p]]=1;dis[pos[p]]=0;
while(!q.empty())
{
int u=q.top();q.pop();
for(int i=last[u];i;i=e[i].nt)
if(dis[e[i].to]>dis[u]+e[i].val)
{
dis[e[i].to]=dis[u]+e[i].val;
if(!book[e[i].to])
{
book[e[i].to]=1;
q.push(e[i].to);
}
}
}
}
int main()
{
n=read();m=read();p=read();
build1(1,1,n);build2(1,1,n);
int u1,v1,u2,v2;
for(int i=1;i<=m;i++)
{
u1=read();v1=read();u2=read();v2=read();
sz++;insert1(1,1,n,u1,v1);insert2(1,1,n,u2,v2);
sz++;insert1(1,1,n,u2,v2);insert2(1,1,n,u1,v1);
}
dijkstra();
for(int i=1;i<=n;i++)printf("%d\n",dis[pos[i]]/2);
return 0;
}
/*
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3
1
1
2
0
1
HINT
*/