Submission #1079459

#TimeUsernameProblemLanguageResultExecution timeMemory
1079459thelegendary08Treatment Project (JOI20_treatment)C++14
0 / 100
29 ms10436 KiB
#include<bits/stdc++.h> #define pb push_back #define int long long #define vi vector<int> #define vvi vector<vector<int>> #define vll vector<long long int> #define vvll vector<vector<long long int>> #define pii pair<int, int> #define vpii vector<pair<int, int>> #define vc vector<char> #define vvc vector<vector<char>> #define vb vector<bool> #define mii map<int,int> #define mll map<long long int, long long int> #define mivi map<int,vector<int>> #define f0r(i,n) for(int i=0;i<n;i++) #define FOR(i,k,n) for(int i=k;i<n;i++) using namespace std; const int mxn = 5005; struct project{ int t, l, r, c; }; int n,m; vi adj[mxn]; bool can(project a, project b){ //cout<<a.t<<' '<<b.t<<"TImE"<<'\n'; if(a.l > b.l)swap(a, b); if(a.r+1 < b.l){ //cout<<a.l<<' '<<b.l<<' '<<a.r<<' '<<b.r<<'\n'; return 0; } if(a.r + 1 == b.l){ return a.t == b.t; } if(a.r >= b.l){ //cout<<(a.l - b.r + 1)/2<<' '<<abs(b.t - a.t)<<'\n'; //cout<< return (a.r - b.l + 1)/((a.l == 1 || b.r == n) ? 1 : 2) >= abs(b.t - a.t); } return 0; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); //ifstream cin(".in"); //ofstream cout(".out"); cin>>n>>m; vector<project>v; f0r(i, m){ int a,b,c,d; cin>>a>>b>>c>>d; v.pb({a,b,c,d}); } //sort(v.begin(), v.end()); f0r(i, m){ FOR(j, i+1, m){ if(can(v[i], v[j])){ adj[i].pb(j); adj[j].pb(i); } } } f0r(i, m){ //for(auto u : adj[i])cout<<u<<' '; //cout<<'\n'; } vi dist(m, 4e18); priority_queue<pii>q; vi endpts; f0r(i, m){ if(v[i].l == 1){ dist[i] = v[i].c; q.push({-v[i].c, i}); } if(v[i].r == n){ endpts.pb(i); } } while(!q.empty()){ int node = q.top().second; q.pop(); for(auto u : adj[node]){ if(dist[u] > dist[node] + v[u].c){ dist[u] = dist[node] + v[u].c; q.push({-dist[u], u}); } } } int ans = 4e18; for(auto u : endpts){ ans = min(ans, dist[u]); } if(ans == 4e18)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...