This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
const ll oo= 1e5+9;
const ll inf=1e18;
struct node
{
ll t,l,r,c;
} a[oo];
bool cmp(const node&A,const node&B)
{
return A.r < B.r;
}
ll n,m,d[5009];
bool vis[5009];
void solve()
{
cin>>n>>m;
for(ll i=0; i<m; i++)
d[i]=inf;
for(ll i=0; i<m; i++)
{
cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c;
if(a[i].l==1)
d[i]=0;
}
while(1)
{
ll id=-1;
for(ll i=0; i<m; i++)
{
if(id==-1)
{
if((!vis[i])&&d[i]<inf)
id=i;
}
else if(d[id]>d[i]&&!vis[i])
id=i;
}
if(id==-1)
break;
// cout<<id<<endl;
// cout<<d[id]<<"? "<<endl;
vis[id]=1;
for(ll i=0; i<m; i++)
{
if(a[i].l<=a[id].r-abs(a[id].t-a[i].t)+1)
d[i]=min(d[i],d[id]+a[id].c);
}
}
ll ans=inf;
for(ll i=0; i<m; i++)
if(a[i].r==n&&vis[i])
ans=min(ans,d[i]+a[i].c);
if(ans>=inf)
ans=-1;
cout<<ans;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
ll tt=1;
// cin>>tt;
while(tt--)
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |