#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int to;
int cost;
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
const int INF = INT_MAX;
vector<vector<Edge>> graph(N);
// Build the graph
for (int i = 0; i < M; ++i) {
graph[x[i]].push_back({y[i], c[i]});
graph[y[i]].push_back({x[i], c[i]});
}
// Dijkstra's algorithm
vector<int> dist(N, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (dist[u] < d) continue;
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.cost;
// Apply special ability if available
if (arr[v] == 2) {
w /= 2;
if (K > 0) {
w = min(w, dist[u]);
K--;
}
} else if (arr[v] == 0) {
w = 0;
}
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
// Return the minimum time to reach Cyberland
return dist[H] == INF ? -1 : dist[H];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
860 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
1420 KB |
Double -7.71503e+08 violates the range [-1, 1e+18] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
1412 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
6984 KB |
Double -3.61975e+08 violates the range [-1, 1e+18] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
1372 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
1460 KB |
Double -1.47238e+09 violates the range [-1, 1e+18] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
1372 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
1368 KB |
Double -3.67931e+08 violates the range [-1, 1e+18] |
2 |
Halted |
0 ms |
0 KB |
- |