Submission #854273

#TimeUsernameProblemLanguageResultExecution timeMemory
854273denniskimTreatment Project (JOI20_treatment)C++17
0 / 100
2 ms856 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) struct gujo { ll T, L, R, C; }; ll n, m; gujo a[5010]; vector<pll> vec[5010]; ll dist[5010]; int main(void) { fastio cin >> n >> m; for(ll i = 1 ; i <= m ; i++) cin >> a[i].T >> a[i].L >> a[i].R >> a[i].C; for(ll i = 1 ; i <= m ; i++) { for(ll j = i + 1 ; j <= m ; j++) { ll L1, R1, L2, R2; if(a[i].T < a[j].T) { L1 = a[i].L + a[j].T - a[i].T; R1 = a[i].R - a[j].T + a[i].T; L2 = a[j].L; R2 = a[j].R; } else { L1 = a[j].L + a[i].T - a[j].T; R1 = a[j].R - a[i].T + a[j].T; L2 = a[i].L; R2 = a[i].R; } if(R2 < L1 - 1 || R1 < L2 - 1) continue; vec[i].push_back({j, a[j].C}); vec[j].push_back({i, a[i].C}); } } for(ll i = 1 ; i <= m ; i++) dist[i] = INF; priority_queue<pll> pq; for(ll i = 1 ; i <= m ; i++) { if(a[i].L == 1) { dist[i] = a[i].C; pq.push({0, i}); } } while(!pq.empty()) { pll qq = pq.top(); pq.pop(); for(auto &i : vec[qq.se]) { if(dist[i.fi] > dist[qq.se] + i.se) { dist[i.fi] = dist[qq.se] + i.se; pq.push({-dist[i.fi], i.fi}); } } } ll ans = INF; for(ll i = 1 ; i <= m ; i++) { if(a[i].R == n) ans = min(ans, dist[i]); } if(ans == INF) cout << -1; else cout << ans; 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...