#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> B(m), P(m);
for (int i = 0; i < m; i++) {
cin >> B[i] >> P[i];
// اگر ورودی 1-based باشه:
// B[i]--;
}
// برای هر موقعیت، سگهایی که اونجا هستن
vector<vector<int>> dogs_at_pos(n);
for (int i = 0; i < m; i++) {
dogs_at_pos[B[i]].push_back(i);
}
vector<int> dist(m, INF);
using pii = pair<int,int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d,u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
if (u == 1) break; // جواب پیدا شد
int bu = B[u], pu = P[u];
int rem = bu % pu;
// همهی موقعیتهایی که دوج u میتونه برسه
for (int x = rem; x < n; x += pu) {
int cost = abs(x - bu) / pu;
// همهی دوجهایی که سر این موقعیت هستن
for (int v : dogs_at_pos[x]) {
int nd = d + cost;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
}
if (dist[1] == INF) cout << -1 << "\n";
else cout << dist[1] << "\n";
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... |