QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463236 | #4363. Branch Assignment | alpha1022 | WA | 1ms | 4360kb | C++14 | 1.5kb | 2024-07-04 16:17:56 | 2024-07-04 16:17:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3;
int n, m, b, k;
vector<pair<int, int>> e0[N + 5], e1[N + 5];
int dis0[N + 5], dis1[N + 5];
void dijkstra(vector<pair<int, int>> *e, int *dis, int s) {
fill_n(dis + 1, n, inf);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.emplace(dis[s] = 0, s);
while (!q.empty()) {
auto [d, u] = q.top(); q.pop();
if (d > dis[u]) continue;
for (auto [v, w] : e[u])
if (dis[v] > dis[u] + w)
q.emplace(dis[v] = dis[u] + w, v);
}
}
ll w[N + 5];
pair<ll, int> f[N + 5];
bool check(ll lim) {
for (int i = 1; i <= b; ++i) {
f[i] = {infll, 0};
for (int j = 0; j < i; ++j) {
auto t = f[j]; t.first += (w[i] - w[j]) * (i - j - 1) + lim, ++t.second, f[i] = min(f[i], t);
}
}
return f[b].second >= k;
}
ll ans;
int main() {
scanf("%d%d%d%d", &n, &b, &k, &m);
for (int i = 1; i <= m; ++i) {
int u, v, w; scanf("%d%d%d", &u, &v, &w), e0[u].emplace_back(v, w), e1[v].emplace_back(u, w);
}
dijkstra(e0, dis0, b + 1), dijkstra(e1, dis1, b + 1);
for (int i = 1; i <= b; ++i) w[i] = dis0[i] + dis1[i];
sort(w + 1, w + b + 1);
for (int i = 1; i <= b; ++i) w[i] += w[i - 1];
ll l = 0, r = 1e15, res = 0;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) r = mid - 1, res = mid;
else l = mid + 1;
}
check(res), printf("%lld\n", f[b].first - res * k);
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4360kb
input:
5 4 2 10 5 2 1 2 5 1 3 5 5 4 5 0 1 5 1 2 3 1 3 2 5 2 4 5 2 1 1 3 4 2
output:
0
result:
wrong answer 1st lines differ - expected: '13', found: '0'