제출 #569263

#제출 시각아이디문제언어결과실행 시간메모리
569263BadPenaltyJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
1 ms1020 KiB
#include <iostream> #include <vector> #include <queue> using namespace std; typedef long long ll; #define F first #define S second #define pb push_back #define endl '\n' #define all(x) x.begin(),x.end() #define yes cout<<"Yes"<<endl #define no cout<<"No"<<endl const int N = 30010,mod = 1e9+7; int vstd[N],dst[N]; pair<int,int>A[N]; vector<int> tile[N]; int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i = 0;i<n;i++)dst[i] = 1e9; for(int i = 0;i<m;i++) { cin>>A[i].F>>A[i].S; tile[A[i].F].pb(i); } priority_queue<pair<int,int>>pq; for(auto u:tile[A[0].F]) pq.push({0,u}); while(!pq.empty()) { int nd = pq.top().S; int jumps = -pq.top().F; int x = A[nd].F; int p = A[nd].S; pq.pop(); if(vstd[nd])continue; vstd[nd] = 1; if(nd==1) { cout<<jumps<<endl; return 0; } int k = 1; for(int i = x+p;i<n;i+=p) { for(auto u:tile[i]) { if(k+jumps<dst[u]) { dst[u] = k+jumps; pq.push({-(k+jumps),u}); } } k++; } k = 1; for(int i = x-p;i>=0;i-=p) { for(auto u:tile[i]) { if(k+jumps<dst[u]) { dst[u] = k+jumps; pq.push({-(k+jumps),u}); } } k++; } } cout<<-1<<endl; 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...