Submission #874458

#	Time	Username	Problem	Language	Result	Execution time	Memory
874458		Darren0724	Treatment Project (JOI20_treatment)	C++17	35 / 100	3098 ms	7504 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define x first
#define y second
const int N=150005;
const int INF=1e18;
struct st{
    int t,l,r,c;
};
int32_t main() {
    int m,n;cin>>m>>n;
    vector<st> v(n);
    for(int i=0;i<n;i++){
        int a,b,c,d;cin>>a>>b>>c>>d;
        v[i]={a,b,c,d};
    }
    vector<int> dis(n,INF);
    priority_queue<pair<int,int>> pq;
    for(int i=0;i<n;i++){
        if(v[i].l==1){
            dis[i]=v[i].c;
            pq.push({-v[i].c,i});
        }
    }
    while(pq.size()){
        auto [d,i]=pq.top();
        pq.pop();
        d=-d;
        if(d!=dis[i]){
            continue;
        }
        for(int j=0;j<n;j++){
            if(j==i){
                continue;
            }
            if(abs(v[i].t-v[j].t)<=v[i].r-v[j].l+1){
                if(dis[j]>dis[i]+v[j].c){
                    dis[j]=dis[i]+v[j].c;
                    pq.push({-dis[j],j});
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++){
        //cout<<dis[i]<<endl;
        if(v[i].r==m){
            ans=min(ans,dis[i]);
        }
    }
    cout<<(ans==INF?-1:ans)<<endl;
    

    return 0;
}
/*
10 5
1 5 10 3
1 1 6 1
1 2 8 3
1 6 10 4
1 1 3 1
*/

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