优化建图，首先分几种情况讨论。假设当前的桥 \(l,r,h\)。起点和终点是 \(S,T\)。
第一种情况：\(S \leq l < r \leq T\)。
容易发现如果要从这条天桥中间上这条天桥，一定经过 \(l\) 或 \(r\)，不如直接走上去。所以只用保留 \((l,h),(r,h)\) 和他们往下的一个其他天桥与该楼的交点，这个交点是为了让它从其它天桥换到更高的这个天桥去的。
第二种情况 \(l < S < r \leq T\) 或 \(S \leq l < T < r\)。
这两种情况对称，以第一种为例。此时有可能从 \(S\) 往左绕上天桥，但是如果中间有足够高的楼能上，就会上该楼去走这个天桥，所以求出高度大于等于 \(h\) ，左右离 \(S\) 最近的楼的坐标 \(x1,x2\)，保留 \((l,h),(x1,h),(x2,h),(r,h)\) 和它们往下的一个交点。
第三种情况 \(l < S < T <r\)。
发现本质上把第二种情况的两个可能都做一遍就行，可以归到第二类情况去。
这样我们就优化了点数和边数。具体实现可以使用 \(set\) 维护满足条件的楼的坐标或点的坐标，按高度排序后扫一遍即可。
没有精细实现，代码常数较大/qd。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10,maxm=4e6+10,inf=1e18;
struct build{int x,h,id;}a[maxn];
int pos[maxn];
struct bridge{int l,r,h;}w[maxn],tn[maxm];
int n,m,S,T,tot,tnode;
struct node{int x,h;}p[maxm];
vector< pair<int,int> > G[maxm];
struct tedge{int u,v,w;};
vector<tedge> E;
priority_queue< pair<int,int> > q;
int dis[maxm];bool vis[maxm];
signed main()
{
// freopen("ex_d2.in","r",stdin);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].h),a[i].x++,a[i].id=i,pos[i]=a[i].x;
for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&w[i].l,&w[i].r,&w[i].h),w[i].l++,w[i].r++;
sort(w+1,w+1+m,[&](bridge a,bridge b){return a.h>b.h;});
sort(a+1,a+1+n,[&](build a,build b){return a.h>b.h;});
int ptr=1;
scanf("%lld%lld",&S,&T);S++;T++;
set< int > st;
for(int i=1;i<=m;i++)
{
while(ptr<=n&&a[ptr].h>=w[i].h)st.insert(a[ptr].id),ptr++;
vector<int> vec;vec.push_back(w[i].l);vec.push_back(w[i].r);
if(S<w[i].r&&w[i].l<S)
{
auto it1=st.lower_bound(S),it2=--st.upper_bound(S);
vec.push_back(*it1),vec.push_back(*it2);
}
if(T<w[i].r&&w[i].l<T)
{
auto it1=st.lower_bound(T),it2=--st.upper_bound(T);
vec.push_back(*it1),vec.push_back(*it2);
}
sort(vec.begin(),vec.end());vec.resize(unique(vec.begin(),vec.end())-vec.begin());
for(int t=1;t<vec.size();t++)tn[++tot]={vec[t-1],vec[t],w[i].h};
}
set< pair<int,int> > sc;
sort(tn+1,tn+1+tot,[&](bridge a,bridge b){return a.h>b.h;});
for(int i=1;i<=tot;i++)
{
int L=tn[i].l,R=tn[i].r,ln,rn;
auto itl=sc.lower_bound({L,0});
vector<int> pnode;
++tnode;ln=tnode;p[tnode]={L,tn[i].h};
pnode.push_back(ln);
while(itl!=sc.end()&&itl->first<=R)
{
++tnode;p[tnode]={itl->first,tn[i].h};pnode.push_back(tnode);
// printf("%d %d %d %d\n",tnode,itl->second,p[itl->second].h,tn[i].h);
E.push_back({tnode,itl->second,p[itl->second].h-tn[i].h});
sc.erase(itl++);
}
++tnode;rn=tnode;p[tnode]={R,tn[i].h};
pnode.push_back(rn);
// printf("!%d %d %d\n",tn[i].l,tn[i].r,tn[i].h);
// for(int v:pnode)printf("%d ",p[v].x);putchar('\n');
for(int t=1;t<pnode.size();t++)
E.push_back({pnode[t-1],pnode[t],pos[p[pnode[t]].x]-pos[p[pnode[t-1]].x]});
sc.insert({L,ln});sc.insert({R,rn});
}
//for(int i=1;i<=tnode;i++)
// printf("%d %d\n",pos[p[i].x],p[i].h);
for(auto [u,v,w]:E){
// printf("%d %d %d\n",u,v,w);
G[u].push_back({v,w}),G[v].push_back({u,w});
}
auto its=sc.lower_bound({S,0});
int snode=++tnode;
if(its->first==S)G[snode].push_back({its->second,p[its->second].h});
auto itt=sc.lower_bound({T,0});
++tnode;
if(itt->first==T)G[itt->second].push_back({tnode,p[itt->second].h});
for(int i=1;i<=tnode;i++)dis[i]=inf;
dis[snode]=0;q.push({0,snode});
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:G[u])
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
if(dis[tnode]==inf)puts("-1");
else printf("%lld\n",dis[tnode]);
}
/*
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
*/