제출 #1275842

#제출 시각아이디문제언어결과실행 시간메모리
1275842random_user27Jakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
601 ms3508 KiB
// In The Name Of God #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define pb push_back #define endl '\n' #define test(x) cout<<x,exit(0) #define fast (ios_base::sync_with_stdio(false),cin.tie(NULL)) const int maxn=3e4+10; const int inf=1e9; const int sq=250; int mark[maxn][sq+5]; int dis[maxn]; vector<int>vec[maxn]; int n,m; int main(){ fast; cin>>n>>m; int start,en; for(int i=1;i<=m;i++){ int b,p;cin>>b>>p; if(i==1){ start=b; } if(i==2){ en=b; } vec[b].pb(p); } for(int i=0;i<n;i++){ dis[i]=inf; } dis[start]=0; priority_queue<pii, vector<pii>, greater<pii>> st; st.push({0,start}); while(st.size()){ int d=st.top().first; int v=st.top().second; st.pop(); if(dis[v]<d){ continue; } for(int ind=0;ind<vec[v].size();ind++){ int p=vec[v][ind]; int cnt=1; for(int i=v+p;i<n;i+=p){ if(dis[i]>dis[v]+cnt){ dis[i]=dis[v]+cnt; st.push({dis[i],i}); } cnt++; } cnt=1; for(int i=v-p;i>=0;i-=p){ if(dis[i]>dis[v]+cnt){ dis[i]=dis[v]+cnt; st.push({dis[i],i}); } cnt++; } } } if(dis[en]>1e7){ cout<<-1<<endl; } else{ cout<<dis[en]<<endl; } }
#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...