#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int dp[30001];
vector<int> G[30001];
int A[30001][2];
bool ok[30001][800][2];
int main(){
int n, k;
cin >> n >> k;
for(int i = 0; i < k; i++){
cin >> A[i][0] >> A[i][1];
G[A[i][0]].push_back(A[i][1]);
}
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
q.push({0, A[0][0], 1 << 30});
fill(dp, dp + n, (1 << 30) - 1);
while(q.size()){
tuple<int, int, int> qe = q.top(); q.pop();
int v = get<0>(qe), w = get<1>(qe), ban = get<2>(qe);
if(dp[v] != (1 << 30)) continue;
dp[v] = w;
// cout << v << ' ' << w << endl;
for(auto i : G[v]){
if(i % ban == 0) continue;
for(int j = v % i; j < n; j += i){
int d = abs(v - j) / i;
if(dp[j] > w + d) q.push({w + d, j, i});
}
}
}
cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |