Submission #41702

#TimeUsernameProblemLanguageResultExecution timeMemory
41702HassoonyJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
870 ms10684 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double D; const int inf=(1<<30); const int MX=30009; vector<int>v[MX]; int dis[MX],vis[MX]; int n,m,b,p,st,en; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&b,&p); v[b].push_back(p); if(i==0)st=b; if(i==1)en=b; } for(int i=0;i<n;i++)dis[i]=inf; dis[st]=0; priority_queue<pair<int,int> >pq; pq.push({0,st}); while(!pq.empty()){ int x=pq.top().second,c=-pq.top().first;pq.pop(); if(vis[x])continue; vis[x]=1; for(auto pp:v[x]){ // cout<<pp<<endl; for(int i=1;i*pp+x<n;i++){ // cout<<i*pp+x<<" "; if(dis[i*pp+x]>c+i){ dis[i*pp+x]=c+i; pq.push({-c-i,i*pp+x}); } } for(int i=1;-i*pp+x>=0;i++){ if(dis[-i*pp+x]>c+i){ dis[-i*pp+x]=c+i; pq.push({-c-i,-i*pp+x}); } } } } if(dis[en]==inf)puts("-1"); else cout<<dis[en]<<endl; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
skyscraper.cpp:13:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&b,&p);
                            ^
#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...