QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625635 | #6306. Chase Game | Hamed5001 | WA | 3ms | 8576kb | C++14 | 2.4kb | 2024-10-09 20:09:56 | 2024-10-09 20:09:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 1, INF = 0x3f3f3f3f;
vector<int> adj[MAXN];
long long DIST[MAXN], BEST[MAXN];
long long DISTN[MAXN];
int N, M, K, D;
void bfs() {
queue<pair<int, int>> q;
q.push({0, K});
DIST[K] = 0;
int mx = 1000;
while (!q.empty() && mx--) {
auto node = q.front(); q.pop();
if (DIST[node.second] < node.first) continue;
for (auto it : adj[node.second]) {
if (DIST[it] < node.first + 1) continue;
q.push({node.first + 1, it});
DIST[it] = node.first + 1;
}
}
q.push({0, N});
DISTN[N] = 0;
while (!q.empty() && mx--) {
auto node = q.front(); q.pop();
if (DISTN[node.second] < node.first) continue;
for (auto it : adj[node.second]) {
if (DISTN[it] < node.first + 1) continue;
q.push({node.first + 1, it});
DISTN[it] = node.first + 1;
}
}
}
long long range(long long n) {
if (n < 1) return 0;
return (n * (n + 1)) >> 1;
}
long long range(int l, int r) {
return range(r) - range(l - 1);
}
long long calc(int node) {
long long ret = 0;
long long full = (DISTN[node] + 1) / D;
ret += full * range(1, D);
if ((DISTN[node] + 1) % D)
ret += range(D - DISTN[node] % D, D);
return ret;
}
long long dijkstra(int st) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, st});
BEST[st] = 0;
long long ans = 0;
while (!pq.empty()) {
auto [cost, node] = pq.top(); pq.pop();
assert(cost >= 0);
if (node == N) return cost;
if (BEST[node] < cost) continue;
for (auto it : adj[node]) {
if (DIST[it] >= D) {
if (BEST[N] > cost + calc(it)) {
BEST[N] = cost + calc(it);
pq.push({cost + calc(it), N});
}
}
else if (BEST[it] > cost + D - DIST[it]) {
BEST[it] = cost + D - DIST[it];
pq.push({cost + D - DIST[it], it});
}
}
}
return -1;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
memset(DIST, INF, sizeof DIST);
memset(DISTN, INF, sizeof DISTN);
memset(BEST, INF, sizeof BEST);
cerr << DIST[0] << endl;
cin >> N >> M >> K >> D;
for (int i = 0; i < M; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs();
cout << dijkstra(1);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 8300kb
input:
5 5 3 1 1 2 2 4 4 5 1 3 3 5
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8532kb
input:
13 17 12 3 1 2 2 3 3 4 4 13 5 13 7 8 7 9 7 10 7 11 7 6 12 7 1 8 8 9 9 10 10 11 11 6 6 13
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 0ms
memory: 8296kb
input:
10 9 4 1 4 3 1 2 7 6 6 5 8 9 9 10 5 4 8 7 3 2
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 2ms
memory: 8304kb
input:
10 20 9 1 9 5 2 9 4 5 10 5 7 3 1 8 7 1 7 5 3 4 3 1 7 8 3 8 9 3 10 6 9 1 1 6 8 5 6 2 1 10 2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 8496kb
input:
10 20 3 1 1 4 6 7 5 4 5 3 2 1 8 1 7 8 2 6 2 4 4 8 9 5 1 10 7 4 5 8 4 10 2 5 6 10 4 6 3 7 1 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 8500kb
input:
10 20 4 1 2 7 6 4 2 3 2 4 6 5 8 5 6 7 10 2 3 10 1 8 3 9 3 7 1 7 5 1 6 1 3 4 2 1 5 2 9 2 9 10
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 0ms
memory: 8336kb
input:
10 20 1 10 10 9 2 5 7 8 7 10 10 8 8 9 5 6 3 1 6 4 7 9 2 3 3 6 2 1 8 6 5 8 7 4 4 3 2 4 4 1 9 6
output:
24
result:
ok 1 number(s): "24"
Test #8:
score: 0
Accepted
time: 2ms
memory: 8528kb
input:
10 20 6 10 5 4 1 7 6 8 1 2 6 1 5 2 5 1 2 4 5 3 3 2 10 3 9 10 7 9 3 1 5 9 1 8 8 3 8 7 6 4 2 7
output:
15
result:
ok 1 number(s): "15"
Test #9:
score: -100
Wrong Answer
time: 3ms
memory: 8576kb
input:
1000 999 387 1 505 506 314 313 410 411 680 681 884 885 491 492 60 59 343 342 396 397 880 881 954 953 833 834 53 54 284 283 794 793 241 240 347 348 89 88 787 786 551 550 673 672 56 57 683 682 168 169 814 813 726 725 877 876 981 982 799 800 228 227 568 569 387 386 211 212 30 29 298 299 514 515 561 562...
output:
-1
result:
wrong answer 1st numbers differ - expected: '999', found: '-1'