#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using bdata = vector<bool>;
using ddata = vector<double>;
using idata = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using gpii = vector<vpii>;
template<typename U, typename V>
using pq = priority_queue<pair<U, V>>;
const double INF = 1e18;
bdata reachable;
gpii roads;
idata type;
void dfs_reach (int node) {
if (reachable[node]) return ;
reachable[node] = true;
for (const auto &road : roads[node])
dfs_reach(road.first);
}
void dijkstra (ddata &distances, int H) {
pq<double, int> queue;
for (int i = 0; i < distances.size(); i ++)
if (distances[i] != INF)
queue.push({ - distances[i], i });
while (queue.size() != 0) {
const auto curr = queue.top(); queue.pop();
double dist = - curr.first;
int node = curr.second;
if (node == H) continue ;
if (distances[node] != dist) continue ;
for (const auto &road : roads[node]) {
int next = road.first;
int ndist = road.second + dist;
if (ndist >= distances[next]) continue ;
distances[next] = ndist;
queue.push({ - ndist, next });
}
}
}
void divide (int N, ddata &distances) {
ddata new_distances(N);
for (int i = 0; i < N; i ++) new_distances[i] = distances[i];
for (int i = 0; i < N; i ++) {
if (!(type[i] == 2 && reachable[i])) continue ;
for (const auto &road : roads[i]) {
double h = (distances[i] / 2.0) + road.second;
new_distances[road.first] = min(
new_distances[road.first],
h
);
}
}
for (int i = 0; i < N; i ++) distances[i] = new_distances[i];
}
ddata create (int N) {
ddata res(N, INF);
for (int i = 0; i < N; i ++)
if (reachable[i] && type[i] == 0)
res[i] = 0;
return res;
}
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) {
type.clear(); type.resize(N);
for (int i = 0; i < N; i ++) type[i] = arr[i];
type[0] = 0;
roads.clear(); roads.resize(N);
for (int i = 0; i < M; i ++) {
roads[x[i]].push_back({ y[i], c[i] });
roads[y[i]].push_back({ x[i], c[i] });
}
reachable.clear(); reachable.resize(N, false);
dfs_reach(0);
if (!reachable[H]) return -1;
ddata values = create(N);
dijkstra(values, H);
//for (int i = 0; i < K; i ++) {
// divide(N, values);
// dijkstra(values, H);
//}
return values[H];
}
Compilation message
cyberland.cpp: In function 'void dijkstra(ddata&, int)':
cyberland.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < distances.size(); i ++)
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
548 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
548 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
26 ms |
620 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
8684 KB |
Double -2.14748e+09 violates the range [-1, 1e+18] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
596 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
544 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
636 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
564 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |