8A2Wa求助

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
int read()
{
    char ch;
    int x=0;
    int k=1;
    ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            k=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
        x=x*10+ch-'0',ch=getchar();
    return x*k;
}
int n,maxn;
int x,y;
struct xxxxx
{
    int u;
    int v;
    int w;
    int next;
} e[1000000];
int f[810000];
int tot=0;
queue <int> qq;
void biu(int a,int b,int c)
{
    tot++;
    e[tot].u=a;
    e[tot].v=b;
    e[tot].w=c;
    e[tot].next=f[a];
    f[a]=tot;
}
struct xxx
{
    int h;
    int l;
    int r;
    int lid;
    int rid;
} a[110000];
int dx,dy;
int ans=0;
int step=0;
int id=0;
int d[210000];
int q[1001001];
int vv[210000];
void spfa(int qd)
{
    int h=1;
    int t=0;
    q[++t]=qd;
    memset(d,0x3f,sizeof(d));
    d[qd]=0;
    vv[qd]=1;
    int now;
    while(h<=t)
    {
        now=q[h++];
        vv[now]=0;
        for(int i=f[now]; i; i=e[i].next)
        {
            if(d[e[i].v]>d[e[i].u]+e[i].w)
            {
                d[e[i].v]=d[e[i].u]+e[i].w;
                if(vv[e[i].v]==0)
                {
                    vv[e[i].v]=1;
                    q[++t]=e[i].v;
                }
            }
        }
    }
}
bool cmp(xxx a,xxx b)
{
    return a.h>b.h;
}
int main()
{
    n=read();
    maxn=read();
    dx=read();
    dy=read();
    for(int i=1; i<=n; i++)
    {
        a[i].h=read();
        a[i].l=read();
        a[i].r=read();
    }
    sort(a+1,a+1+n,cmp);
    id=1;
    a[0].h=dy;
    a[0].l=dx;
    a[0].lid=1;
    qq.push(0);
    while(!qq.empty())
    {
        int dq;
        dq=qq.front();
        qq.pop();
        if(dq!=0)
        {
            for(int i=dq+1; i<=n; i++)
            {
                if(a[i].l<=a[dq].l&&a[dq].l<=a[i].r&&a[i].h+maxn>=a[dq].h)
                {
                    if(a[i].lid==0)
                    {
                        id++;
                        biu(a[dq].lid,id,a[dq].h-a[i].h+a[dq].l-a[i].l);
                        a[i].lid=id;
                        id++;
                        biu(a[dq].lid,id,a[dq].h-a[i].h+a[i].r-a[dq].l);
                        a[i].rid=id;
                        qq.push(i);
                    }
                    else
                    {
                        biu(a[dq].lid,a[i].lid,a[dq].h-a[i].h+a[dq].l-a[i].l);
                        biu(a[dq].lid,a[i].rid,a[dq].h-a[i].h+a[i].r-a[dq].l);
                    }
                    break;
                }
            }
            for(int i=dq+1; i<=n; i++)
            {
                if(a[i].l<=a[dq].r&&a[dq].r<=a[i].r&&a[i].h+maxn>=a[dq].h)
                {
                    if(a[i].rid==0)
                    {
                        id++;
                        biu(a[dq].rid,id,a[dq].h-a[i].h+a[dq].r-a[i].l);
                        a[i].lid=id;
                        id++;
                        biu(a[dq].rid,id,a[dq].h-a[i].h+a[i].r-a[dq].r);
                        a[i].rid=id;
                        qq.push(i);
                    }
                    else
                    {
                        biu(a[dq].rid,a[i].lid,a[dq].h-a[i].h+a[dq].r-a[i].l);
                        biu(a[dq].rid,a[i].rid,a[dq].h-a[i].h+a[i].r-a[dq].r);
                    }
                    break;
                }
            }
        }
        else
        {
            for(int i=dq+1; i<=n; i++)
            {
                if(a[dq].h>=a[i].h&&a[i].l<=a[dq].l&&a[dq].l<=a[i].r)
                {
                    id++;
                    biu(a[dq].lid,id,a[dq].h-a[i].h+a[dq].l-a[i].l);
                    a[i].lid=id;
                    id++;
                    biu(a[dq].lid,id,a[dq].h-a[i].h+a[i].r-a[dq].l);
                    a[i].rid=id;
                    qq.push(i);
                    break;
                }
            }
        }
    }
    spfa(1);
    int minn=2147483647;
    for(int i=n; i>=1; i--)
    {
        if(a[i].h<=maxn)
        {
            if(minn>d[a[i].lid]+a[i].h && !f[a[i].lid])
                minn=d[a[i].lid]+a[i].h;
            if(minn>d[a[i].rid]+a[i].h && !f[a[i].rid])
                minn=d[a[i].rid]+a[i].h;
        }
        else break;
    }
    printf("%d",minn);
    return 0;
}