博客园可能食用更佳
学校内部模拟赛出了这题，顺便来写下题解。
惊奇的发现题解区居然全是建图跑最短路，这怎么行，所以这一篇题解并没有跑任何最短路，而是使用了线段树优化 DP。
考虑将建边区间按右端点从小到大排序，每次以右端点为枚举编号，记作 \(x\) ，发现只会从 \([1,x-1]\) 中的点转移过来，故这样对区间排序后不会存在后效性，故可以开始规划 DP。
将区间从小到大排序后，记第 \(i\) 个区间为 \([L_i,R_i]\)，\(dp_x\) 表示从点 \(1\) 出发到达点 \(x\) 的最短距离，则
\[dp_{R_i}= \begin{cases} \min_{j=L_i}^{R_i-1} dp_j+W_i &, R_i \geq 2 \\ 0 &, R_i=1 \\ \end{cases} \]这样做的时间复杂度为 \(\mathcal O(mn+m \log m)\)，那么就可以考虑优化一下复杂度
观察到 \(dp_{R_i}\) 需要快速查询 \(dp_{L_i,\dots,R_i-1}\) 的最小值，并且需要更新 \(dp_{R_i}\) 的值，故可以使用线段树区间查询最小值，单点修改即可，时间复杂度 \(O(m \log m + m \log n)\)，其中 \(m \log m\) 为排序的时间复杂度，\(\log n\) 为线段树单次操作的时间复杂度，细节见代码
#include<bits/stdc++.h>
#define il inline
#define ls u<<1
#define rs u<<1|1
#define int long long//注意数据范围，需要开 long long
using namespace std;
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m;
struct dat
{
int L,R,W;
}a[N];
struct SGT//常规线段树操作
{
int t[N<<2];
void push_up(int u)
{
t[u]=min(t[ls],t[rs]);
}
void build(int u,int l,int r)
{
if(l==r) return t[u]=(l==1)?0:INF,void();//初始化 dp[1]=0
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int x,int k)
{
if(x==l&&r==x) return t[u]=k,void();//单点修改，故不用 push_down
int mid=(l+r)>>1;
if(x<=mid) update(ls,l,mid,x,k);
else update(rs,mid+1,r,x,k);
push_up(u);
}
int query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return t[u];
int mid=(l+r)>>1,res=INF;
if(x<=mid) res=min(res,query(ls,l,mid,x,y));
if(y>mid) res=min(res,query(rs,mid+1,r,x,y));
return res;
}
}T;
template <typename T>
il void read(T &x)
{
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
signed main()
{
read(n),read(m);
T.build(1,1,n);//建树
for(int i=1;i<=m;i++)
read(a[i].L),read(a[i].R),read(a[i].W);
sort(a+1,a+1+m,[](dat a,dat b){return a.R<b.R;});//按照右端点从小到大排序
for(int i=1;i<=m;i++)
{
if(a[i].L==a[i].R) continue;//特判区间大小为 1 的情况
int pre=T.query(1,1,n,a[i].L,a[i].R-1);//查询区间 [L_i,R_i-1] 的最小值
int now=T.query(1,1,n,a[i].R,a[i].R);//查询 dp[R_i] 的值
if(pre+a[i].W<now) T.update(1,1,n,a[i].R,pre+a[i].W);//若从前面转移过来更优，则修改
//当然这里也可以直接在线段树上修改取 min 也行
}
int ans=T.query(1,1,n,n,n);//dp[n]
printf("%lld",ans==INF?-1:ans);
return 0;
}