#include <bits/stdc++.h>
#define llint long long
#define fi first
#define se second
#define BIT(x, i) ((x>>i)&1ll)
#define MASK(i) (1ll<<i)
#define db(x) cout << #x << " = " << x << endl;
using namespace std;
void openFile() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
#ifdef Tr___
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#else
//freopen("tname.inp", "r", stdin);
//freopen("tname.out", "w", stdout);
#endif
}
template <typename T>
inline void read(T &ret){
register char c = getchar(); bool neg = false; ret = 0;
while (c < '0' || c > '9'){ if (c == '-') neg = true; c = getchar(); }
while (c >= '0' && c <= '9'){ ret = (ret << 1) + (ret << 3) + c - '0';
c = getchar(); }
if (neg) ret = -ret;
}
template <typename T>
void write(T x){
if (x < 0){ putchar('-'); x = -x; }
if (x >= 10) write(x / 10); putchar(x % 10 + 48);
}
const int maxn = 3e4 + 5;
const int maxm = 1e6 + 5;
const llint inf = 1e9 + 7;
const int maxk = 2000;
int N, M;
int b[maxn], p[maxn];
vector<int> vertex[maxn];
int edge[maxn][maxk];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
bool inq[maxn];
int d[maxn];
void enter() {
read(N); read(M);
for (int i = 1; i <= M; ++i) {
read(b[i]); read(p[i]);
//if (p[i] < maxk) {
// if (!edge[b[i]][p[i]]) {
// edge[b[i]][p[i]] = true;
// for (int j = b[i]; j >= 1; j -= p[i]) {
// edge[j][p[i]] = true;
// }
// for (int j = b[i]; j <= N; j += p[i]) {
// edge[j][p[i]] = true;
// }
// }
//}
//else {
vertex[b[i]].push_back(p[i]);
//}
}
}
void solve() {
fill_n(d, maxn, inf);
d[0] = 0;
//inq[0] = true;
q.push(make_pair(0, 0));
while (!q.empty()) {
int u = q.top().se;
if (q.top().fi > d[u]) continue;
q.pop();
//inq[u] = false;
//for (int k = 1; k < maxk; ++k) {
// if (edge[u][k]) {
// int v = u + k;
// if (v < N && d[v] > d[u] + 1) {
// d[v] = d[u] + 1;
// if (!inq[v]) {
// q.push(v);
// inq[v] = true;
// }
// }
// v = u - k;
// if (v >= 0 && d[v] > d[u] + 1) {
// d[v] = d[u] + 1;
// if (!inq[v]) {
// q.push(v);
// inq[v] = true;
// }
// }
// }
//}
for (auto k : vertex[u]) {
for (int j = u; j < N; j += k) {
if (d[j] > d[u] + (j - u) / k) {
d[j] = d[u] + (j - u) / k;
if (!inq[j]) {
q.push(make_pair(d[j], j));
//inq[j] = true;
}
}
}
for (int j = u; j >= 0; j -= k) {
if (d[j] > d[u] + (u - j) / k) {
d[j] = d[u] + (u - j) / k;
if (!inq[j]) {
q.push(make_pair(d[j], j));
//inq[j] = true;
}
}
}
}
}
if (d[1] == inf) d[1] = -1;
cout << d[1] << endl;
}
int main() {
openFile();
enter();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
237676 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
237676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
237676 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
237676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
237676 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
237676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
237676 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
237676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
237676 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
237676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
