| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 876286 | vjudge1 | Treatment Project (JOI20_treatment) | C++17 | 0 ms | 0 KiB |
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 pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,t[maxn],l[maxn],r[maxn],c[maxn],d[maxn];
priority_queue<pli,vector<pli>,greater<pli>>pq;
vector<ll>g[maxn];
void solve()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
{
cin >> t[i] >> l[i] >> r[i] >> c[i];
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
if(i==j) continue;
if(t[i]<=t[j])
{
if(l[j]<=r[i]-(t[j]-t[i])+1) g[i].pb(j);
}
else
{
if(r[i]>=l[j]+(t[i]-t[j])-1) g[i].pb(j);
}
}
}
for(int i=1;i<=m;i++)
{
d[i]=inf;
if(l[i]==1)
{
d[i]=c[i];
pq.push({d[i],i});
seg[0].update(pos[i],inf);
seg[1].update(pos[i],inf);
}
}
while(!pq.empty())
{
ll u=pq.top().se;
ll W=pq.top().fi;
pq.pop();
if(W>d[u]) continue;
if(r[u]==n) {cout << W;return;}
for(int v:g[u])
{
if(d[v]>d[u]+c[v])
{
d[v]=d[u]+c[v];
pq.push({d[v],v});
}
}
}
cout << -1;
}
int main()
{
fastio
//freopen("c.INP","r",stdin);
//freopen("c.OUT","w",stdout);
solve();
}