QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#765271 | #6306. Chase Game | FangYifan | WA | 1ms | 3860kb | C++20 | 2.2kb | 2024-11-20 13:31:01 | 2024-11-20 13:31:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
constexpr int mod = 998244353;
constexpr int N = 1e6 + 10;
void solve() {
int n, m, k, d;
cin >> n >> m >> k >> d;
vector<vector<int>> edge(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
auto calc = [&](ll len) -> ll {
ll sum1 = 1ll * (len / d) * d * (d + 1) / 2;
ll sum2 = 1ll * (len % d) * (d + d - len % d + 1) / 2;
return sum1 + sum2;
};
auto bfs = [&](int s) -> vector<int> {
vector<int> dis(n + 1, 1e9);
queue<int> q;
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : edge[u]) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis;
};
ll ans = 1e18;
vector<int> disn = bfs(n);
vector<int> disk = bfs(k);
vector<ll> dis(n + 1, 1e18), vis(n + 1);
priority_queue<pair<ll, int>> q;
for (auto x : edge[1]) {
if (disk[x] >= d) {
ans = min(ans, calc(disn[x] + 1));
// cerr << x << ' ' << disn[x] << ' ' << calc(disn[x]) << "\n";
} else {
dis[x] = d - disk[x];
q.push({-dis[x], x});
}
}
while (!q.empty()) {
auto [d, u] = q.top(); q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto v : edge[u]) {
if (disk[v] >= d) {
ans = min(ans, dis[u] + calc(disn[v] + 1));
// cerr << u << ' ' << v << ' ' << dis[u] << ' ' << calc(disn[v]) << "\n";
} else if (dis[v] > dis[u] + d - disk[v]) {
dis[v] = dis[u] + d - disk[v];
q.push({-dis[v], v});
}
}
}
cout << min(ans, dis[n]) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
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: 3564kb
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: 3492kb
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: 0ms
memory: 3516kb
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: 0ms
memory: 3860kb
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: 3508kb
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: -100
Wrong Answer
time: 0ms
memory: 3568kb
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:
28
result:
wrong answer 1st numbers differ - expected: '24', found: '28'