Submission #1001405

#TimeUsernameProblemLanguageResultExecution timeMemory
1001405aaaaaarrozJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n,m; cin>>n>>m; vector<vector<ll>>dist(m,vector<ll>(n,LLONG_MAX)); for(ll i=0;i<m;i++){ ll b,p; cin>>b>>p; dist[i][b]=0; if(i==1){ continue; } ll j=b-p; while(j>=0){ dist[i][j]=dist[i][j+p]+1; j-=p; } j=b+p; while(j<n){ dist[i][j]=dist[i][j-p]+1; j+=p; } } vector<vector<pair<ll,ll>>>graph(m,vector<pair<ll,ll>>()); for(ll i=0;i<m;i++){ for(ll j=i+1;j<m;j++){ for(ll k=0;k<n;k++){ if(dist[i][k]!=LLONG_MAX&&dist[j][k]!=LLONG_MAX){ graph[i].push_back({j,dist[i][k]+dist[j][k]}); graph[j].push_back({i,dist[i][k]+dist[j][k]}); } } } } priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq; vector<ll>distancias(m,LLONG_MAX); distancias[0]=0; pq.push({0,0}); while(!pq.empty()){ auto[peso,nodo]=pq.top(); pq.pop(); for(auto[vecino,w]:graph[nodo]){ if((peso+w)<distancias[vecino]){ distancias[vecino]=peso+w; pq.push({distancias[vecino],vecino}); } } } cout<<((distancias[1]!=LLONG_MAX)?distancias[1]:-1)<<"\n"; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...