题目传送门

卧槽这题有点牛逼。

像我这种蒟蒻只看题面肯定没有什么头绪，所以只好看一眼数据范围，似乎只能依赖方案在 O(mlog) 内解决。

至于为什么会想到 dp ，应该只能靠感觉吧，这题一看就很有线性dp的味道。

所以由前面的想法可以大概先设个 fi ，至于 i 的含义只能结合方案的性质和所求的东西来考虑。

先整理一下：一个方案由四个参数 Ti,Li,Ri,Ci确定，而我们需要最小化 [1,n] 全部被覆盖的代价和。

那么 i 的含义只和 Ti,Li,Ri 有关，而我们的最终状态中没有时间的限制，而 Li,Ri 在地位上是对等的，所以我们不妨只从 Ri 考虑对 i 含义的设计。

接下来这一步应该只能靠经验了，因为最终状态是全部覆盖，所以可以看成是由前缀全部覆盖递推而来，落到状态设计上就是设 fi 为覆盖前缀 [1,Ri] 的最小代价。

这样就可以自然的写出方程：

fi=minRj−Li+1≥|Tj−Ti|fj+Ci

残念ながら…这是一个有后效性的方程，似乎并不能按照某种拓扑序转移，这时就要用上另一个套路。

给方程换一种写法：

fi≤fj+Ci,Rj−Li+1≥|Tj−Ti|

观察到方程很像一个三角不等式，启发我们往最短路去想，这时麻烦的只有边数是 O(m2) 的，这时只能挖掘这张图的性质。

注意到 (这一步真的很自然) i 的所有入边权都是 Ci ，所以在 Dijkstra 中每个点只应被更新一次就可以得到最短路，剩下的都是无用更新，至多只有 O(m) 次松弛。

所以我们要做的事情就是每次取出优先队列的一个点，只松弛未被松弛过且满足条件的点，那么接下来就好做了，对于上面那个条件式子很容易用线段树维护。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long;
const int N=1e5+10;
int rd(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }return x;
}
int n,m;
struct D{
    int t,l,r,c;
    int f0(){return -t+l-1;}
    int f1(){return t+l-1;}
}a[N];
ll f[N];
#define pii pair<ll,int>
priority_queue<pii,vector<pii>,greater<pii> >q;
struct st{
    struct node{
        int l,r,m;
        int v[2];
    }d[N<<2|1];
    void pushup(int p){
        int l=p<<1,r=l|1;
        d[p].v[0]=min(d[l].v[0],d[r].v[0]);
        d[p].v[1]=min(d[l].v[1],d[r].v[1]);
    }
    void build(int p,int l,int r){
        d[p]={l,r,l+r>>1,0};
        if(l==r){
            if(a[l].l==1){
                f[l]=a[l].c,q.push({f[l],l});
                d[p].v[0]=d[p].v[1]=2e9;
                return;
            }
            d[p].v[0]=a[l].f0();
            d[p].v[1]=a[l].f1();
            return;
        }
        build(p<<1,l,d[p].m);
        build(p<<1|1,d[p].m+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int lim,int x,int op){
        if(l>r||lim<d[p].v[op])return;
        if(d[p].l==d[p].r){
            f[d[p].l]=f[x]+a[d[p].l].c;
            q.push({f[d[p].l],d[p].l});
            d[p].v[0]=d[p].v[1]=2e9;
            return ;
        }
        if(l<=d[p].m)modify(p<<1,l,r,lim,x,op);
        if(r>d[p].m)modify(p<<1|1,l,r,lim,x,op);
        pushup(p);
    }
}t;
int main(){
    m=rd(),n=rd();
    for(int i=1;i<=n;++i){
        a[i]={rd(),rd(),rd(),rd()};
        f[i]=1e18;
    }
    sort(a+1,a+1+n,[](D x,D y)->bool{return x.t<y.t;});
    t.build(1,1,n);
  
    while(!q.empty()){
        int x=q.top().second;q.pop();
        t.modify(1,1,x-1,a[x].r-a[x].t,x,0);
        t.modify(1,x+1,n,a[x].r+a[x].t,x,1);
    }
    ll ans=1e18;
    for(int i=1;i<=n;++i){
        if(a[i].r==m)
            ans=min(ans,f[i]);
    }
    printf("%lld\n",(ans==1e18)?-1:ans);
    return 0;
}