이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000000
int main() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
for (int i = 0; i < m; ++i) cin >> b[i] >> p[i];
vector<bool> exists(n);
for (int i = 0; i < m; ++i) exists[b[i]] = true;
vector<vector<int>> ed(n, vector<int>(n, oo));
for (int i = 0; i < m; ++i){
int cnt = 0;
for (int j = b[i] + p[i]; j < n; j += p[i]) {
cnt++;
if (exists[j]) ed[b[i]][j] = min(ed[b[i]][j], cnt);
}
for (int j = b[i] - p[i]; j >= 0; j -= p[i]){
cnt++;
if (exists[j]) ed[b[i]][j] = min(ed[b[i]][j], cnt);
}
}
vector<int> d(n, oo); d[b[0]] = 0;
vector<bool> visited(n);
for (int i = 0; i < n; ++i){
int mn = -1;
for (int j = 0; j < n; ++j){
if (!visited[j] && (mn == -1 || d[mn] > d[j])) mn = j;
}
visited[mn] = true;
for (int j = 0; j < n; ++j){
if (visited[j]) continue;
if (d[j] > d[mn] + ed[mn][j]) d[j] = d[mn] + ed[mn][j];
}
}
int ans = d[b[1]];
if (ans == oo) ans = -1;
cout << ans << "\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... |