首页 > 其他分享 >BZOJ 3073: [Pa2011]Journeys 线段树优化最短路

BZOJ 3073: [Pa2011]Journeys 线段树优化最短路

时间:2023-07-07 13:38:01浏览次数:50  
标签:ch Journeys int Pa2011 read 3073 Seter include dis



3073: [Pa2011]Journeys


Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 243  Solved: 80

[Submit][Status][Discuss]

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


区间建边

线段树优化最短路,高级吧

BZOJ 3073: [Pa2011]Journeys 线段树优化最短路_#include

#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
*/




标签:ch,Journeys,int,Pa2011,read,3073,Seter,include,dis
From: https://blog.51cto.com/u_16181403/6651993

相关文章

  • [刷题笔记] Luogu P3073 [USACO13FEB]Tractor S
    ProblemSolution和汽车拉力比赛差不多,思路都是二分,二分\(d\),但是汽车拉力比赛从一个路标开始搜即可,本题没有给定起点。一条合法路径起点是未知的,不得随便从一个点开始搜,否则可能找不到正确路径。怎么处理呢?容易想到对于每一个二分的\(d\),开一个\(n^2\)的循环,从每一个点开始搜......
  • kaldi在linux上编译,Ubuntu 12.04下编译安装Kaldi https://blog.csdn.net/we
    因为同事工作需要kaldi,所以安装过程有点麻烦。在此记录一下折腾的过程。OS:Ubuntu 12.04(amd64)kaldi的下载地址 http://svn.code.sf.net/p/kaldi/code/ 我这里下......