제출 #219411

#제출 시각아이디문제언어결과실행 시간메모리
219411maruii치료 계획 (JOI20_treatment)C++14
0 / 100
3083 ms3188 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using tii = array<int, 3>; using pil = pair<int, ll>; #define ff first #define ss second #define eack emplace_back #define all(x) (x).begin(), (x).end() const ll INF = 1e18; int N, M; map<int, vector<pair<pii, int>>> MP; using abc = pair<ll, tii>; abc in[100005]; priority_queue<abc, vector<abc>, greater<abc>> pq; map<tii, ll> dist; bool chk(tii a, tii b) { if (a[0] > b[0]) swap(a, b); int l = b[1] - 1, r = b[2] + 1; int s = a[1], e = a[2]; if (s > 1) s += b[0] - a[0]; if (e < N) e -= b[0] - a[0]; return l <= e && s <= r; } tii f(tii a, tii b) { if (a[0] > b[0]) swap(a, b); if (a[1] > 1) a[1] += b[0] - a[0]; if (a[2] < N) a[2] -= b[0] - a[0]; return {b[0], min(a[1], b[1]), max(a[2], b[2])}; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N >> M; for (int i = 1; i <= M; ++i) { int t, l, r, c; cin >> t >> l >> r >> c; in[i] = {c, {t, l, r}}; if (l == 1) { pq.push(in[i]); tii n = {t, l, r}; if (!dist.count(n)) dist[n] = c; else dist[n] = min(dist[n], (ll)c); } } while (pq.size()) { auto x = pq.top(); pq.pop(); ll c = x.ff; int t = x.ss[0], l = x.ss[1], r = x.ss[2]; tii v = {t, l, r}; if (r == N) return !printf("%lld", c); if (c > dist[v]) continue; for (int i = 1; i <= M; ++i) if (chk(v, in[i].ss)) { tii n = f(v, in[i].ss); if (n == v) continue; if (!dist.count(n) || dist[n] > c + in[i].ff) { dist[n] = c + in[i].ff; pq.emplace(c + in[i].ff, n); } } } cout << -1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...