评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const int Mod = 998244353;

int read() {
    int x;
    scanf("%lld",&x);
    return x;
}

int n,m;
struct Interval {
    int tim,l,r,pay;
} a[N];

vector<int>G[N];
int dis[N];
bool vis[N];

void dijkstra() {
    memset(dis,0x3f,sizeof dis);
    priority_queue<pii,vector<pii>,greater<pii>>q;
    for(int i=1; i<=n; i++) {
        if(a[i].l==1) {
            dis[i]=a[i].pay;
            q.push({dis[i],i});
        }
    }
    while(!q.empty()) {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int y:G[x]) {
            if(dis[y]>dis[x]+a[y].pay) {
                dis[y]=dis[x]+a[y].pay;
                q.push({dis[y],y});
            }
        }
    }
}

signed main() {
    m=read();
    n=read();
    for(int i=1; i<=n; i++) {
        int tim=read(),l=read(),r=read(),pay=read();
        a[i]= {tim,l,r,pay};
    }
    sort(a+1,a+n+1,[](Interval x,Interval y) {
        if(x.tim!=y.tim) return x.tim<y.tim;
        else if(x.l!=y.l) return x.l<y.l;
        else return x.r<y.r;
    });
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(a[j].r-a[i].l+1>=a[j].tim-a[i].tim && a[i].r-a[j].l+1>=a[j].tim-a[i].tim) {
                G[i].push_back(j);
                G[j].push_back(i);
//				cout<<i<<' '<<j<<'\n';
            }
        }
    }
    dijkstra();
    int ans=inf;
    for(int i=1; i<=n; i++) {
        if(a[i].r==m) ans=min(ans,dis[i]);
    }
    cout<<(ans==inf?-1:ans);
    return 0;
}