제출 #1196235

#제출 시각아이디문제언어결과실행 시간메모리
1196235ezzzayJakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
343 ms327680 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second #define pb push_back const int N=3e5+5; bool vis[N]; vector<pair<int,int>>v[N]; int dst[N]; int X[N]; signed main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x,p; cin>>x>>p; X[i]=x; p=abs(p); for(int j=1;j<=n;j++){ if(x-p*j>=0)v[x].pb({x-p*j,j}); if(x+p*j<n)v[x].pb({x+p*j,j}); } } for(int i=0;i<N;i++){ dst[i]=1e14; } dst[X[0]]=0; priority_queue<pair<int,int>>q; q.push({0,X[0]}); while(!q.empty()){ auto [w,a]=q.top(); q.pop(); w=-w; if(dst[a]<w)continue; for(auto [b,c]:v[a]){ if(dst[b]>dst[a]+c){ dst[b]=dst[a]+c; q.push({-dst[b],b}); } } } if(dst[X[1]]==1e14)dst[X[1]]=-1; cout<<dst[X[1]]; }
#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...