rt，使用线段树优化建图+vector存图+01 bfs最短路，MLE on #35，求助

空间使用：约$4 \times10^6$个vector<pair<int,bool> >+约$4 \times10^6$个int+约$4 \times10^6$大小的bitset+1个list(deque也试过了，没有用)。

自认为马蜂海星的code：

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pc(x) putchar(x)

template<typename T> inline void fr(T& num){
	num=0;short sign=1;char ch=std::getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')sign=-1;
		ch=std::getchar();
	}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num=num*sign;
}
template<typename T>inline void fw(T x){
	if(x<0)std::putchar('-'),x=-x;
	if(x>9)fw(x/10);
	std::putchar(x%10+'0');
}

const int N=1<<19,M=N<<2;
vector<pair<int,bool> > g[N<<3];
int n,m,p;
int dis[N<<3];
bitset<N<<3> vis;

inline void bfs(int s){
	list<int> dq;
	memset(dis,0x3f,sizeof dis);
	dis[s]=0,dq.emplace_back(s);
	while(dq.size()){
		int x=dq.front();dq.pop_front();
		if(vis[x])continue;
		vis[x]=1;
		for(auto [y,z]:g[x]){
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				if(z)dq.emplace_back(y);
				else dq.emplace_front(y);
			}
		}
	}
}

namespace seg{
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
	inline void build(int p,int l,int r){
		if(l==r){
			g[p].emplace_back(p+M,0);
			g[p+M].emplace_back(p,0);
			return;
		}
		g[p].emplace_back(ls(p),0);
		g[p].emplace_back(rs(p),0);
		g[ls(p)+M].emplace_back(p+M,0);
		g[rs(p)+M].emplace_back(p+M,0);
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
	}
	inline void adde(int p,int from,int l,int r,int _l,int _r){
		if(l<=_l&&_r<=r)return g[from].emplace_back(p,1),void();
		int mid=(_l+_r)>>1;
		if(l<=mid)adde(ls(p),from,l,r,_l,mid);
		if(r>mid) adde(rs(p),from,l,r,mid+1,_r);
	}
	inline void add(int p,int l,int r,int L,int R,int _l,int _r){
		if(l<=_l&&_r<=r)return adde(1,p+M,L,R,1,n);
		int mid=(_l+_r)>>1;
		if(l<=mid)add(ls(p),l,r,L,R,_l,mid);
		if(r>mid)add(rs(p),l,r,L,R,mid+1,_r);
	}
	inline void query(int p,int pos,int _l,int _r){
		if(_l==_r)return bfs(p+M);
		int mid=(_l+_r)>>1;
		if(pos<=mid)query(ls(p),pos,_l,mid);
		else query(rs(p),pos,mid+1,_r);
	}
	inline void out(int p,int _l,int _r){
		if(_l==_r)return fw(dis[p]),pc('\n'),void();
		int mid=(_l+_r)>>1;
		out(ls(p),_l,mid);
		out(rs(p),mid+1,_r);
	}
}

void solve(){
	fr(n),fr(m),fr(p);
	seg::build(1,1,n);
	for(int i=1;i<=m;i++){
		int a,b,c,d;fr(a),fr(b),fr(c),fr(d);
		seg::add(1,a,b,c,d,1,n);
		seg::add(1,c,d,a,b,1,n);
	}
	seg::query(1,p,1,n);
	seg::out(1,1,n);
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int Count=1;//fr(Count);
	while(Count--)solve();
}
/*
多测不清空，OI见祖宗。
multitesting without clearing,oier meets the LCA.
十年OI一场空，不开LL见祖宗。
Ten years of OI just AFO,no #define int long long sees the LCA.
似是神犇成才处，实为蒟蒻黄泉路。
It is likely to be the Au medal for the big old,but in fact it is the Si medal for me.
黄题有恨无正解，码力不若小学生。
A yellow problem I can't AC,codeforces is not as NB as EUlar Shai.
今生无奈入OI，来世不做信竞人。
This life I am a Silly Being in oi,next life I won't f**k the sh*t of infomatics.
*/