WA #47 #59求调

#include <iostream>
#include <queue>
#define ll long long
using namespace std;
ll n, s, t, l[1005], r[1005], h[1005], dp[1005][5], tot = 0, hea[100005], v[100005], dis[100005];
priority_queue<pair<ll, ll> > q;
struct Edge{
	ll next, to, dis;
} edge[100005];
void add(ll a, ll b, ll c){
	edge[++tot] = Edge{hea[a], b, c};
	hea[a] = tot;
	return ; 
}
void dij(ll s){
    for (ll i = 1; i <= 2 * n; i++){
        v[i] = 0;
        dis[i] = 1e10;
    }
    q.push(make_pair(0, s));
    dis[s] = 0;
    while (!q.empty()){
        ll x = q.top().second;
        q.pop();
        if (v[x]){
            continue;
        }
        v[x] = 1;
        for (ll i = hea[x]; i; i = edge[i].next){
            ll y = edge[i].to, z = edge[i].dis;
            if (dis[x] + z < dis[y]){
                dis[y] = dis[x] + z;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
    return ;
}
int main(){
	cin >> n >> s >> t;
	for (ll i = 1; i <= n; i++){
		cin >> l[i] >> r[i] >> h[i];
	}
	for (ll i = 1; i <= n; i++){
		ll mx = 0, mxj = 0;
		for (ll j = 1; j <= n; j++){
			if (h[j] < h[i] && l[j] <= l[i]){
				if (h[j] > mx){
					mx = h[j];
					mxj = j;
				}
			}
		}
		if (mxj != 0){
			add(i, mxj, h[i] - mx + l[i] - l[mxj]);
            add(i, mxj + n, h[i] - mx + r[mxj] - l[i]);
            //cout << i << " " << mxj << " " << h[i] - mx + l[i] - l[mxj] << " " << h[i] - mx + r[mxj] - l[i] << endl;
		}
	}
    //cout << endl;
	for (ll i = 1; i <= n; i++){
		ll mx = 0, mxj = 0;
		for (ll j = 1; j <= n; j++){
			if (h[j] < h[i] && r[j] >= r[i]){
				if (h[j] > mx){
					mx = h[j];
					mxj = j;
				}
			}
		}
		if (mxj != 0){
			add(i + n, mxj + n, h[i] - mx + r[mxj] - r[i]); 
            add(i + n, mxj, h[i] - mx + r[i] - l[mxj]);
            //cout << i << " " << mxj << " " << h[i] - mx << " " << h[i] - mx + r[mxj] - r[i] << " " << h[i] - mx + r[i] - l[mxj] << endl;
		}
	}
	for (ll i = 1; i <= n; i++){
		add(i, i + n, r[i] - l[i]);
		add(i + n, i, r[i] - l[i]);
	}
	dij(s);
	ll ans = min(dis[t], dis[t + n]);
	if (ans >= 1e10){
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;
	return 0;
}