이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 10;
priority_queue<int> pos[maxn];
vector<pair<int, int>> g[maxn];
int d[maxn];
int dijkstra(int src, int snk) {
memset(d, 1, sizeof d);
d[src] = 0;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> Q;
Q.push({0, src});
while (!Q.empty()) {
auto q = Q.top(); Q.pop();
if (q.second == snk) return q.first;
if (q.first != d[q.second]) continue;
for (auto e : g[q.second]) {
int temp = q.first + e.second;
if (temp < d[e.first]) {
d[e.first] = temp;
Q.push({temp, e.first});
}
}
}
return -1;
}
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a;
priority_queue<pair<int, int>> t;
for (int i = 0; i < m; ++i) {
int b, p;
cin >> b >> p;
t.push({p, b});
pos[b].push(p);
}
auto same = [](int b, int p) {
return !pos[b].empty() && pos[b].top() == p;
};
while (!t.empty()) {
auto q = t.top(); t.pop();
pos[q.second].pop();
if (same(q.second, q.first)) continue;
for (int i = 1; ; ++i) {
int temp = q.second + i * q.first;
if (temp >= n) break;
g[q.second].emplace_back(temp, i);
if (same(temp, q.first)) break;
}
for (int i = 1; ; ++i) {
int temp = q.second - i * q.first;
if (temp < 0) break;
g[q.second].emplace_back(temp, i);
if (same(temp, q.first)) break;
}
}
cout << dijkstra(0, 1) << endl;
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... |