QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625651 | #6306. Chase Game | Hamed5001 | WA | 0ms | 8296kb | C++14 | 2.3kb | 2024-10-09 20:13:10 | 2024-10-09 20:13:15 |
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;
while (!q.empty()) {
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()) {
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: 0
Wrong Answer
time: 0ms
memory: 8296kb
input:
5 5 3 1 1 2 2 4 4 5 1 3 3 5
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'