Submission #1126430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126430		ttamx	Treatment Project (JOI20_treatment)	C++20	35 / 100	1685 ms	589824 KiB

treatment

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using  P =pair<ll,int>;

const int N=1e5+5;
const ll INF=LLONG_MAX/2;

int n,m;
int t[N],l[N],r[N],c[N];
vector<int> adj[N];
priority_queue<P,vector<P>,greater<P>> pq;
ll dist[N];
ll ans=INF;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> m >> n;
    for(int i=1;i<=n;i++){
        cin >> t[i] >> l[i] >> r[i] >> c[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            if(t[i]<=t[j]){
                if(r[i]+t[i]>=l[j]+t[j]-1){
                    adj[i].emplace_back(j);
                }
            }else{
                if(r[i]-t[i]>=l[j]-t[j]-1){
                    adj[i].emplace_back(j);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        dist[i]=INF;
    }
    for(int i=1;i<=n;i++){
        if(l[i]==1){
            dist[i]=c[i];
            pq.emplace(c[i],i);
        }
    }
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(d>dist[u])continue;
        for(auto v:adj[u]){
            ll nd=d+c[v];
            if(nd<dist[v]){
                dist[v]=nd;
                pq.emplace(nd,v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(r[i]==m){
            ans=min(ans,dist[i]);
        }
    }
    cout << (ans<INF?ans:-1LL);
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61