【CF827F】DirtyArkady'sKitchenDP

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1000010;
int n,m,tot,ans;
int mx[maxn],mn[maxn],fir[maxn];
struct edge
{
	int a,b,l,r;
}p[maxn<<1];
queue q;
vector v[maxn];
inline void add(int a,int b,int c,int d)
{
	p[++tot].a=a,p[tot].b=b,p[tot].l=c+((c^a)&1),p[tot].r=d-((d^b)&1);
}
bool cmp(const edge &a,const edge &b)
{
	return a.l}
inline void solve(int x)
{
	int a=p[x].a,b=p[x].b,l=p[x].l=max(p[x].l,mn[a]),r=p[x].r;
	if(mx[a]	{
		v[a].push_back(x);
		return ;
	}
	q.push(x);
	while(!q.empty())
	{
		x=q.front(),q.pop(),a=p[x].a,b=p[x].b,l=p[x].l,r=p[x].r;
		if(l>=r)	continue;
		if(mx[b]+2		else	mx[b]=max(mx[b],r);
		if((b>>1)==n)	ans=min(ans,mn[b]);
		while(fir[b]<(int)v[b].size())
		{
			int t=v[b][fir[b]];
			if(mx[b]>=p[t].l)	fir[b]++,q.push(t),p[t].l=mn[b];
			else	break;
		}
	}
}
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}
	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();
	return ret*f;
}
int main()
{
	n=rd(),m=rd();
	if(n==1)
	{
		puts("0");
		return 0;
	}
	int i,a,b,c,d;
	for(i=1;i<=m;i++)
	{
		a=rd(),b=rd(),c=rd(),d=rd();
		add(a<<1,b<<1|1,c,d);
		add(a<<1|1,b<<1,c,d);
		add(b<<1,a<<1|1,c,d);
		add(b<<1|1,a<<1,c,d);
	}
	sort(p+1,p+tot+1,cmp);
	memset(mx,0xc0,sizeof(mx)),memset(mn,0xc0,sizeof(mn));
	mn[2]=mx[2]=0,ans=1<<30;
	for(i=1;i<=tot;i++)	solve(i);
	if(ans==(1<<30))	puts("-1");
	else	printf("%d",ans);
	return 0;
}//5 4 1 2 0 10 2 3 0 10 3 4 0 10 4 5 0 10