#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> p(n);
int f, s, z;
for (int i = 0; i < m; i++) {
int b, c;
cin >> b >> c;
if (i == 0) f = b, s = c;
if (i == 1) z = b;
if (c > n) c = n;
p[b].push_back(c);
}
vector<unordered_map<int, int>> d(n);
d[f][s] = 0;
deque<pair<int, int>> dq;
dq.emplace_front(f, s);
while (!dq.empty()) {
auto [b, c] = dq.front();
if (b == z) {
cout << d[b][c];
return 0;
}
dq.pop_front();
for (int i : p[b]) {
if (!d[b].count(i) || d[b][c] < d[b][i]) {
d[b][i] = d[b][c];
dq.emplace_front(b, i);
}
}
if (b - c >= 0 && (!d[b - c].count(c) || d[b - c][c] > d[b][c] + 1)) {
d[b - c][c] = d[b][c] + 1;
dq.emplace_back(b - c, c);
}
if (b + c < n && (!d[b + c].count(c) || d[b + c][c] > d[b][c] + 1)) {
d[b + c][c] = d[b][c] + 1;
dq.emplace_back(b + c, c);
}
}
cout << -1;
return 0;
}
# | 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... |