题解：Shortest Path on a Line

Rem_CandleFire · 2024-11-28 11:12:19 · 题解

题目传送门

这是一篇线段树优化 DP 的题解，无需最短路算法。

考虑将建边区间按左端点排序，然后枚举点 i。发现对于枚举的 i，它并不会从 [i+1,n] 中的点转移而来，这说明 DP 是无后效性的，那么就可以从 i 转移到后面的点去。

那么我们设 f_i 表示走到 i 的最短路。那么对于建边区间 [i,r]，对于 j\in[l+1,r]，有转移 f_{j}=\min(f_j,f_i+w)。这相当于区间 [i+1,r] 对 f_i+w 取 \min。发现只需要维护这一个操作，所以考虑给区间 [i+1,r] 在线段树上打上标记，那么对于 f_{i+1}，它的值就从线段树的根节点一路取 \min 到达叶节点就行了。标记是永久的，无需下传。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+5;
const LL Inf=1e18;
int n,m;
struct Interval { int l,r,w; } a[N];
bool cmp(Interval a,Interval b) { return a.l==b.l?a.r<b.r:a.l<b.l; }
LL f[N];
struct SegmentTree
{
    struct node { LL tag,val; } tr[N<<2];
    void Build(int l,int r,int k)
    {
        if(l==r) return tr[k].val=(l==1?0:Inf),void();
        int mid=(l+r)>>1;
        Build(l,mid,k<<1); Build(mid+1,r,k<<1|1);
    }
    void Update(int l,int r,int k,int x,int y,LL v)
    {
        if(r<x||l>y) return ;
        if(x<=l&&r<=y)
        {
            if(tr[k].tag>0) tr[k].tag=min(tr[k].tag,v);
            else tr[k].tag=v;
            return ;
        }
        int mid=(l+r)>>1;
        Update(l,mid,k<<1,x,y,v);
        Update(mid+1,r,k<<1|1,x,y,v);
    }
    LL Query(int l,int r,int k,int pos,LL v)
    {
        if(tr[k].tag) v=min(v,tr[k].tag);
        if(l==r) return tr[k].val=min(tr[k].val,v);
        int mid=(l+r)>>1;
        if(pos<=mid) return Query(l,mid,k<<1,pos,v);
        else return Query(mid+1,r,k<<1|1,pos,v); 
    }
} S;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) 
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
    sort(a+1,a+1+m,cmp);
    if(a[1].l!=1) return !puts("-1");
    S.Build(1,n,1);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        f[i]=S.Query(1,n,1,i,Inf);
        while(now<=m&&a[now].l==i) S.Update(1,n,1,a[now].l+1,a[now].r,f[i]+a[now].w),now++;
    }
    if(f[n]==Inf) puts("-1");
    else printf("%lld",f[n]);
    return 0;
}