제출 #1028623

#제출 시각아이디문제언어결과실행 시간메모리
1028623vjudge1Jakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1071 ms145744 KiB
#include<bits/stdc++.h> using namespace std; const int inf = 1e9; int main() { int n, m; cin >> n >> m; int dist[n][m]; for(int i = 0; i < n; i ++) for(int j = 0; j < m ; j++) dist[i][j] = inf; vector<int> L[n]; int p[m], b[m]; for(int i = 0; i < m; i ++) { cin >> b[i] >> p[i]; L[b[i]].push_back(i); } deque<pair<int,int> > Q; Q.push_back({b[0], 0}); dist[b[0]][0] = 0; while(Q.size()) { int f = Q.front().first, s = Q.front().second; Q.pop_front(); // cerr << f << ' ' << s << ' ' << dist[f][s] << endl; for(int res : L[f]) if(dist[f][s] < dist[f][res]) { dist[f][res] = dist[f][s]; Q.push_front({f, res}); } // L[f].clear(); if(f + p[s] < n && dist[f][s] + 1 < dist[f + p[s]][s]) { dist[f + p[s]][s] = dist[f][s] + 1; Q.push_front({f + p[s], s}); } if(f - p[s] >= 0 && dist[f][s] + 1 < dist[f - p[s]][s]) { dist[f - p[s]][s] = dist[f][s] + 1; Q.push_front({f - p[s], s}); } } if(dist[b[1]][1] == inf) cout << -1 << endl; else cout << dist[b[1]][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...