首先考虑一个简单的 (n^2) dp，令 (f_i) 表示在 (t_i) 天， (1) 到 (r_i) 的所有人都已经被治疗完毕了的最小花费。
然后考虑 Dijkstra 一样的方式进行 dp，每次找到所有尚未松弛的 (i) 中 (f_i) 最小的那个进行转移，可以从 (i) 向 (j) 转移的条件是 (r_i-l_j+1 ge |t_i-t_j|)（非常容易理解）.
最后只需找到满足 (r_i=n) 的所有 (f_i) 的最小值即可。
于是得到了复杂度为 (O(m^2)) 的做法。
然后考虑优化这一个过程。
对转移条件的绝对值进行分类讨论后可以简化为：
若 (t_i ge t_j) 为 (r_i-t_i+1 ge l_j-t_j)
若 (t_i<t_j) 为 (r_i+t_i+1 ge l_j+t_j)
然后考虑对所有治疗方案按 (t_i) 排序，维护一个堆来确定转移顺序，每次转移的时候分为两段在线段树上查询，可以保证正确性。
由于采用了类似 Dijkstra 的转移方式，(f_i) 只与向他转移的 (f_j) 的大小有关，可以保证每个点只需要被转移到一次，然后只要在线段树上把对应点的权值设为 (inf) 即可。
于是得到了复杂度为 (O(mlog m)) 的做法。
Code((O(m^2))):
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s
",__LINE__,__FUNCTION__)
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define INF ((int)1e18)
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair<int,int> pii;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
#define N 5005
int t[N],l[N],r[N],w[N];
int f[N],vis[N],n,m;
int get()
{
int pos=0;
for(int i=1;i<=m;i++)
{
if(vis[i]) continue;
if(f[i]<f[pos]) pos=i;
}
return pos;
}
signed main()
{
cin>>n>>m;
for(int i=0;i<=m;i++) f[i]=INF;
for(int i=1;i<=m;i++)
{
t[i]=read(),l[i]=read(),r[i]=read(),w[i]=read();
if(l[i]==1) f[i]=w[i];
}
int pos=get();
while(pos)
{
vis[pos]=1;
for(int i=1;i<=m;i++)
{
if(r[pos]-l[i]>=abs(t[pos]-t[i])-1)
{
int R=f[pos]+w[i];
if(R<f[i]) f[i]=R;
}
}
pos=get();
}
int ans=INF;
for(int i=1;i<=m;i++)
{
if(r[i]==n&&f[i]<ans) ans=f[i];
}
if(ans==INF) cout<<"-1
";
else cout<<ans<<endl;
return 0;
}
Code((O(mlog m))):
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s
",__LINE__,__FUNCTION__)
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define INF ((int)1e18)
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair<int,int> pii;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
#define N 100005
struct Node{int t,l,r,w;};
Node a[N];
bool cmp(Node x,Node y){return x.t<y.t;}
int n,m,f[N];
priority_queue<pii,vector<pii>,greater<pii>> q;
vector<int> v;
struct Seg_tr
{
#define ls (u<<1)
#define rs (u<<1|1)
int tx[N*4],ty[N*4];
void pushup(int u)
{
tx[u]=min(tx[ls],tx[rs]);
ty[u]=min(ty[ls],ty[rs]);
}
void update(int u,int l,int r,int p,int dx,int dy)
{
if(l==r)
{
tx[u]=dx,ty[u]=dy;
return ;
}
int mid=(l+r)/2;
if(p<=mid) update(ls,l,mid,p,dx,dy);
else update(rs,mid+1,r,p,dx,dy);
pushup(u);
}
void queryx(int u,int l,int r,int L,int R,int d)
{
if(l>r) return ;
if(tx[u]>d) return ;
if(l==r)
{
v.pb(l); return ;
}
int mid=(l+r)/2;
if(mid>=L) queryx(ls,l,mid,L,R,d);
if(mid<R) queryx(rs,mid+1,r,L,R,d);
}
void queryy(int u,int l,int r,int L,int R,int d)
{
if(l>r) return ;
if(ty[u]>d) return ;
if(l==r)
{
v.pb(l); return ;
}
int mid=(l+r)/2;
if(mid>=L) queryy(ls,l,mid,L,R,d);
if(mid<R) queryy(rs,mid+1,r,L,R,d);
}
};
Seg_tr t;
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) a[i].t=read(),a[i].l=read(),a[i].r=read(),a[i].w=read();
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(a[i].l==1)
{
f[i]=a[i].w;
t.update(1,1,m,i,INF,INF);
q.push(mp(f[i],i));
}
else
{
f[i]=INF;
t.update(1,1,m,i,a[i].l+a[i].t,a[i].l-a[i].t);
}
}
while(!q.empty())
{
pii u=q.top(); q.pop();
int pos=u.sec;
if(f[pos]!=u.fir) continue;
v.clear();
t.queryy(1,1,m,1,pos-1,a[pos].r-a[pos].t+1);
t.queryx(1,1,m,pos+1,m,a[pos].r+a[pos].t+1);
for(int i:v)
{
int R=u.fir+a[i].w;
if(R<f[i])
{
f[i]=R;
q.push(mp(f[i],i));
t.update(1,1,m,i,INF,INF);
}
}
}
int ans=INF;
for(int i=1;i<=m;i++)
{
if(a[i].r==n&&f[i]<ans) ans=f[i];
}
if(ans==INF) cout<<"-1
";
else cout<<ans<<endl;
return 0;
}