#include <vector>
#include <queue>
#include <limits>
using namespace std;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<double> distances(N, numeric_limits<double>::infinity());
distances[0] = 0;
// Priority queue to store (distance, node)
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
pq.push({0, 0});
// Main Dijkstra's algorithm loop
while (!pq.empty()) {
double dist = pq.top().first;
int node = pq.top().second;
pq.pop();
// Check if we've reached Cyberland
if (node == H) {
return dist;
}
// Check if the current node has the divide-by-2 ability
if (arr[node] == 2 && K > 0) {
// Consider using the divide-by-2 ability
double new_dist = dist / 2.0;
// If using the ability leads to a shorter path, update distance
if (new_dist < distances[node]) {
distances[node] = new_dist;
// Push the updated distance to the priority queue
pq.push({new_dist, node});
// Decrement the remaining uses of divide-by-2 ability
K--;
}
}
// Iterate through neighbors of the current node
for (int i = 0; i < M; i++) {
int neighbor;
if (x[i] == node) {
neighbor = y[i];
} else if (y[i] == node) {
neighbor = x[i];
} else {
continue;
}
// Calculate the new distance to the neighbor
double new_dist = dist + c[i];
// Update the distance if it's shorter
if (new_dist < distances[neighbor]) {
distances[neighbor] = new_dist;
pq.push({new_dist, neighbor});
}
}
}
// If Cyberland is not reachable
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
604 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
348 KB |
Correct. |
2 |
Correct |
33 ms |
344 KB |
Correct. |
3 |
Correct |
30 ms |
348 KB |
Correct. |
4 |
Correct |
33 ms |
512 KB |
Correct. |
5 |
Correct |
31 ms |
524 KB |
Correct. |
6 |
Correct |
55 ms |
724 KB |
Correct. |
7 |
Correct |
156 ms |
740 KB |
Correct. |
8 |
Correct |
244 ms |
1116 KB |
Correct. |
9 |
Correct |
18 ms |
348 KB |
Correct. |
10 |
Correct |
18 ms |
344 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
348 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
662 ms |
2880 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
348 KB |
Correct. |
2 |
Correct |
23 ms |
348 KB |
Correct. |
3 |
Correct |
25 ms |
348 KB |
Correct. |
4 |
Correct |
90 ms |
636 KB |
Correct. |
5 |
Correct |
15 ms |
344 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
348 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
348 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1975 ms |
860 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |