#include <bits/stdc++.h>
/*
--> Author: Kazuki_Hoshino__8703 <--
I love Nanasaki Ai ☆*: .。. o(≒_≒)o .。.:☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
using namespace std;
const int mn = 3e4 + 5, bm = (1 << 11) + 1, mod = 1532023, offset = 5e4;
const int inf = 1e9, base = 311;
int n, m, a[mn], b[mn];
int d[mn][2005];
vector <int> speed[mn];
void dijkstra(){
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>> > pq;
fill(&d[0][0], &d[0][0] + mn * 2005, inf);
d[a[0]][b[0]] = 0;
pq.push({d[a[0]][b[0]], {a[0], b[0]}});
while(pq.size()){
auto[c, i] = pq.top();
auto[u, sp] = i;
pq.pop();
if(c > d[u][sp]) continue;
if(u + sp < n && d[u + sp][sp] > d[u][sp] + 1){
d[u + sp][sp] = d[u][sp] + 1;
pq.push({d[u + sp][sp], {u + sp, sp}});
}
if(u - sp >= 0 && d[u - sp][sp] > d[u][sp] + 1){
d[u - sp][sp] = d[u][sp] + 1;
pq.push({d[u - sp][sp], {u - sp, sp}});
}
for(auto qq : speed[u]){
if(d[u][qq] > d[u][sp]){
d[u][qq] = d[u][sp];
pq.push({d[u][qq], {u, qq}});
}
}
}
int res = inf;
for(int sp = 0; sp <= 2000; sp++) res = min(res, d[a[1]][sp]);
if(res == inf) res = -1;
cout << res << '\n';
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i];
speed[a[i]].push_back(b[i]);
}
dijkstra();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("ROBOT.INP", "r")) {
freopen("ROBOT.INP", "r", stdin);
freopen("ROBOT.OUT", "w", stdout);
}
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | freopen("ROBOT.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen("ROBOT.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |