#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define sz(v) ((int)(v).size())
#define pb push_back
const int N = 1e5;
vector<array<ll, 2>> adj[N];
bitset<N> v, ps;
ll mind1[N], mind2[N], sme[N];
ld md[N];
ll inf = 1e18;
void
dfs(int x, int h) {
if (x == h) return;
if (ps[x]) return;
ps[x] = 1;
for (auto u : adj[x])
dfs(u[0], h);
}
double
solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
for (int i = 0; i < n; ++i) {
sme[i] = inf;
mind2[i] = inf;
mind1[i] = 0;
while (sz(adj[i]))
adj[i].pop_back();
}
v = 0;
ps = 0;
if (h == 0) return 0;
for (int i = 0; i < m; ++i) {
adj[x[i]].pb({y[i], c[i]});
if (y[i] != h)
sme[x[i]] = min(sme[x[i]], (ll)c[i]);
adj[y[i]].pb({x[i], c[i]});
if (x[i] != h)
sme[y[i]] = min(sme[y[i]], (ll)c[i]);
}
dfs(0, h);
priority_queue<array<ll, 2>> q;
for (int i = 1; i < n; ++i) {
if (arr[i] == 0 && ps[i]) {
q.push({0, i});
mind1[i] = 0;
}
else
mind1[i] = inf;
}
q.push({0, 0});
while (sz(q)) {
auto u = q.top();
q.pop();
if (v[u[1]]) continue;
if (u[1] == h) continue;
v[u[1]] = 1;
for (auto x : adj[u[1]]) {
if (mind1[u[1]]+ x[1] < mind1[x[0]]) {
mind1[x[0]] = mind1[u[1]]+ x[1];
q.push({-mind1[x[0]], x[0]});
}
}
}
if (mind1[h] > 1e17) return -1;
long double ans = mind1[h];
while (sz(q)) q.pop();
mind2[h] = 0;
q.push({0, h});
v = 0;
while (sz(q)) {
auto u = q.top();
q.pop();
if (v[u[1]]) continue;
v[u[1]] = 1;
for (auto x : adj[u[1]]) {
if (mind2[u[1]]+ x[1] < mind2[x[0]]) {
mind2[x[0]] = mind2[u[1]]+ x[1];
q.push({-mind2[x[0]], x[0]});
}
}
}
int cn = min(k, 200);
for (int i = 0; i < n; ++i) {
md[i] = mind1[i];
}
priority_queue<pair<ld, int>> qq;
while (cn--) {
while (sz(qq)) qq.pop();
v = 0;
for (int i = 1; i < n; ++i) {
if (arr[i] == 2 && ps[i]) {
qq.push({-(md[i] / ((ld) 2)), i});
}
}
while (sz(qq)) {
auto u = qq.top();
qq.pop();
if (v[u.second]) continue;
if (u.second == h) continue;
v[u.second] = 1;
for (auto x : adj[u.second]) {
if (md[u.second] + ((ld)x[1]) < md[x[0]]) {
md[x[0]] = md[u.second] + ((ld)x[1]);
qq.push({-md[x[0]], x[0]});
}
}
}
ans = min(ans, md[h]);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
86 ms |
2764 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2964 KB |
Correct. |
2 |
Correct |
27 ms |
2900 KB |
Correct. |
3 |
Correct |
25 ms |
2900 KB |
Correct. |
4 |
Correct |
27 ms |
2936 KB |
Correct. |
5 |
Correct |
26 ms |
2900 KB |
Correct. |
6 |
Correct |
24 ms |
4052 KB |
Correct. |
7 |
Correct |
33 ms |
4004 KB |
Correct. |
8 |
Correct |
17 ms |
5136 KB |
Correct. |
9 |
Correct |
41 ms |
2764 KB |
Correct. |
10 |
Correct |
32 ms |
2776 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
2912 KB |
Correct. |
2 |
Correct |
31 ms |
2936 KB |
Correct. |
3 |
Correct |
26 ms |
2920 KB |
Correct. |
4 |
Correct |
34 ms |
2764 KB |
Correct. |
5 |
Correct |
34 ms |
2784 KB |
Correct. |
6 |
Correct |
8 ms |
3804 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
62 ms |
10360 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3008 KB |
Correct. |
2 |
Correct |
23 ms |
3040 KB |
Correct. |
3 |
Correct |
23 ms |
3036 KB |
Correct. |
4 |
Correct |
24 ms |
4396 KB |
Correct. |
5 |
Correct |
30 ms |
2788 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3028 KB |
Correct. |
2 |
Correct |
20 ms |
3048 KB |
Correct. |
3 |
Correct |
35 ms |
10920 KB |
Correct. |
4 |
Correct |
17 ms |
4100 KB |
Correct. |
5 |
Correct |
27 ms |
2768 KB |
Correct. |
6 |
Correct |
25 ms |
3044 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
39 ms |
3020 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
117 ms |
3008 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |