#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double
solve (int n, int m, int k, int h,
std::vector<int> x, std::vector<int> y, std::vector<int> c,
std::vector<int> arr)
{
vector < vector < pair < int, int > > > adj (n);
for (int i = 0; i < m; ++i)
{
adj[x[i]].push_back ({ c[i], y[i] });
adj[y[i]].push_back ({ c[i], x[i] });
}
if (n <= 3)
{
vector < double > da (n, -1);
auto dfs = [&] (auto self, int v, int p, double d) -> void
{
if (arr[v] == 0) d = 0;
if (arr[v] == 2) d /= 2;
bool stop = false;
if (da[v] >= 0) stop = true;
da[v] = d;
if (stop) return;
for (auto &x : adj[v])
if (x.second != p)
self (self, x.second, v, d + x.first);
};
dfs (dfs, 0, -1, 0);
return da[h];
}
priority_queue < pair < ll, int > > q;
q.push ({ 0ll, 0 });
vector < ll > sda (n, -1);
while (q.size ())
{
auto x = q.top ();
q.pop ();
if (sda[x.second] != -1) continue;
sda[x.second] = -x.first;
if (x.second == h) continue;
for (auto &y : adj[x.second])
q.push ({ x.first - y.first, y.second });
}
if (sda[h] == -1) return -1;
set < int > rz;
rz.insert (0);
for (int i = 0; i < n; ++i)
if (arr[i] == 0 && sda[i] > 0)
rz.insert (i);
set < int > rd;
for (int i = 0; i < n; ++i)
if (arr[i] == 2 && sda[i] > 0)
rd.insert (i);
vector < ll > eda (n, -1);
q.push ({ 0ll, h });
while (q.size ())
{
auto x = q.top ();
q.pop ();
if (eda[x.second] != -1) continue;
eda[x.second] = -x.first;
for (auto &y : adj[x.second])
q.push ({ x.first - y.first, y.second });
}
double ans = 1e18;
for (auto &x : rz) ans = min (ans, (double) eda[x]);
// vector < ll > dda (n, -1);
// vector < ll > bfd (n, (ll) 1e18);
// priority_queue < pair < ll, pair < int, int > > > pq;
// for (auto &x : rd) pq.insert ({ 0ll, make_pair (x, x) });
// while (pq.size ())
// {
// auto x = q.top ();
// q.pop ();
// if (x.second.first == h) continue;
// if (dda[x.second.first] == -1 || dda[x.second.first] == -x.first)
// bfd[x.second.second] = min (bfd[x.second.second], -x.first);
// if (dda[x.second.first] != -1) continue;
// dda[x.second.first] = -x.first;
// for (auto &y : adj[x.second.first])
// q.push ({ x.first - y.first, make_pair (y.second, x.second.first) });
// }
// for (auto &x : rd)
// {
// bfd[x]
// }
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
15 ms |
608 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
604 KB |
Correct. |
2 |
Correct |
34 ms |
592 KB |
Correct. |
3 |
Correct |
31 ms |
604 KB |
Correct. |
4 |
Correct |
32 ms |
604 KB |
Correct. |
5 |
Correct |
38 ms |
572 KB |
Correct. |
6 |
Correct |
28 ms |
1556 KB |
Correct. |
7 |
Correct |
39 ms |
1440 KB |
Correct. |
8 |
Correct |
16 ms |
2768 KB |
Correct. |
9 |
Correct |
28 ms |
348 KB |
Correct. |
10 |
Correct |
28 ms |
348 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
604 KB |
Correct. |
2 |
Correct |
34 ms |
600 KB |
Correct. |
3 |
Correct |
33 ms |
604 KB |
Correct. |
4 |
Correct |
31 ms |
344 KB |
Correct. |
5 |
Correct |
33 ms |
348 KB |
Correct. |
6 |
Correct |
7 ms |
1372 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
29 ms |
6608 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
600 KB |
Correct. |
2 |
Correct |
30 ms |
600 KB |
Correct. |
3 |
Correct |
36 ms |
604 KB |
Correct. |
4 |
Correct |
32 ms |
1368 KB |
Correct. |
5 |
Incorrect |
24 ms |
348 KB |
Wrong Answer. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
604 KB |
Correct. |
2 |
Correct |
27 ms |
604 KB |
Correct. |
3 |
Correct |
31 ms |
7816 KB |
Correct. |
4 |
Correct |
20 ms |
1208 KB |
Correct. |
5 |
Incorrect |
28 ms |
348 KB |
Wrong Answer. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
36 ms |
600 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
31 ms |
568 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |