#include<bits/stdc++.h>
#define inline inline __attribute__ ((always_inline))
using namespace std;
const int MAXN=1005;
int n,s,t,dis[2*MAXN];
vector<vector<pair<int,int>>>ed(2*MAXN);
deque<int>q;
class BOARD{
    public:
        int high,l,r;
        int id;
}boa[MAXN];
inline bool cmp(BOARD x,BOARD y){
    if(x.high!=y.high)return x.high>y.high;
    return x.l<y.l;
}
inline void add_line(int fro,int to,int di){ed[fro].push_back(make_pair(to,di));}
inline int L(int id){return 2*id;}
inline int R(int id){return 2*id+1;}
inline void init(){
    for(int i=1;i<=n;i++)
        cin>>boa[i].l>>boa[i].r>>boa[i].high,boa[i].id=i;
    sort(boa+1,boa+1+n,cmp);
    bool f=1;
    for(int i=1;i<=n;i++){
        if(boa[i].id==s&&f)s=i,f=0;
        if(boa[i].id==t){t=i;break;}
    }
    for(int i=s;i<t;i++){
        add_line(L(i),R(i),boa[i].r-boa[i].l);
        add_line(R(i),L(i),boa[i].r-boa[i].l);
        for(int j=i+1;j<=t;j++)
            if(boa[i].high>boa[j].high&&boa[i].l>boa[j].l&&boa[i].l<boa[j].r){
                add_line(L(i),L(j),boa[i].high-boa[j].high+boa[i].l-boa[j].l);
                break;
            }
        for(int j=i+1;j<=t;j++)
            if(boa[i].high>boa[j].high&&boa[i].r>boa[j].l&&boa[i].r<boa[j].r){
                add_line(R(i),R(j),boa[i].high-boa[j].high+boa[j].r-boa[i].r);
                break;
            }
    }
}
inline void SPFA(){
    dis[L(s)]=0;
    int num=1,sum=0;
    q.push_front(L(s));
    while(!q.empty()){
        while(dis[q.front()]*num<sum){
            q.push_back(q.front());
            q.pop_front();
        }
        int cur=q.front();
        q.pop_front();
        sum-=dis[cur];num--;
        for(pair<int,int>i:ed[cur])
            if(dis[i.first]>dis[cur]+i.second){
                dis[i.first]=dis[cur]+i.second;
                sum+=dis[i.first];
                num++;
                if(dis[i.first]>dis[q.front()])q.push_back(i.first);
                else q.push_front(i.first);
            }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>s>>t;
    init();
    SPFA();
    if(dis[L(t)]==0x3f3f3f3f&&dis[R(t)]==0x3f3f3f3f)cout<<-1;
    else cout<<min(dis[L(t)],dis[R(t)]);
    return 0;
}

1 条评论

  • 1

信息

ID
2790
难度
8
分类
(无)
标签
递交数
19
已通过
5
通过率
26%
上传者