Submission #941836

#TimeUsernameProblemLanguageResultExecution timeMemory
941836Tuanlinh123Treatment Project (JOI20_treatment)C++17
35 / 100
837 ms524288 KiB
#include<bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=100005, inf=1e18; vector <ll> A[maxn]; ll x[maxn], l[maxn], r[maxn], w[maxn], dis[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m; cin >> n >> m; for (ll i=1; i<=m; i++) cin >> x[i] >> l[i] >> r[i] >> w[i], dis[i]=inf; for (ll i=1; i<=m; i++) for (ll j=1; j<=m; j++) if (l[j]<=r[i]-abs(x[i]-x[j])+1) A[i].pb(j); priority_queue <pll, vector <pll>, greater<pll>> q; for (ll i=1; i<=m; i++) if (l[i]==1) dis[i]=w[i], q.push({dis[i], i}); while (!q.empty()) { ll u=q.top().se, disu=q.top().fi; q.pop(); if (dis[u]!=disu) continue; for (ll v:A[u]) if (dis[v]>disu+w[v]) dis[v]=disu+w[v], q.push({dis[v], v}); } ll ans=inf; for (ll i=1; i<=m; i++) if (r[i]==n) ans=min(ans, dis[i]); if (ans==inf) cout << "-1"; else cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...