#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pii>> graph(N);
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]});
}
// Priority queue to store (time, country) pairs, sorted by time.
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<vector<double>> dist(N, vector<double>(K + 1, INT_MAX));
dist[0][0] = 0; // Distance to country 0 is 0, and no divide-by-2 ability used.
// Push initial state into the priority queue.
pq.push({0, 0});
while (!pq.empty()) {
int time = pq.top().first;
int country = pq.top().second;
pq.pop();
if (country == H) // Reached Cyberland
return time;
// Check if using divide-by-2 ability is allowed at this country
for (int k = 0; k <= K; ++k) {
int next_time = (k < K) ? time / 2 : time; // If allowed, divide time by 2
if (next_time < dist[country][k]) {
dist[country][k] = next_time;
pq.push({next_time, country});
}
}
// Explore neighbors
for (auto& neighbor : graph[country]) {
int next_country = neighbor.first;
int next_time = time + neighbor.second;
// Check if special ability of the country exists
if (arr[next_country] == 0)
next_time = 0; // Special ability makes passing time 0
else if (arr[next_country] == 2)
next_time /= 2; // Special ability divides passing time by 2
// Relaxation
if (next_time < dist[next_country][0]) {
dist[next_country][0] = next_time;
pq.push({next_time, next_country});
}
}
}
return -1; // Cyberland is not reachable
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
91 ms |
620 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1909 ms |
1136 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1325 ms |
1064 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
890 ms |
21444 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1179 ms |
1224 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
615 ms |
848 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
979 ms |
828 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1044 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |