#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;
for (int i = 0; i < m; i++) {
int b, c;
cin >> b >> c;
if (i == 0 && b - c < 0 && b + c >= n) {
cout << -1;
return 0;
}
if (i == 0) f = b, s = c;
if (c < n) p[b].push_back(c);
}
vector<vector<int>> d(n, vector<int>(n, INT_MAX));
d[f][s] = 0;
deque<pair<int, int>> dq;
dq.emplace_front(f, s);
while (!dq.empty()) {
auto [b, c] = dq.front();
dq.pop_front();
for (int i : p[b]) {
if (d[b][c] < d[b][i]) {
d[b][i] = d[b][c];
dq.emplace_front(b, i);
}
}
if (b - c >= 0 && 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][c] > d[b][c] + 1) {
d[b + c][c] = d[b][c] + 1;
dq.emplace_back(b + c, c);
}
}
int ans = *min_element(d[1].begin(), d[1].end());
if (ans == INT_MAX) ans = -1;
cout << ans;
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... |