#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Node {
int country;
int passing_time;
int divide_count;
Node(int c, int t, int d) : country(c), passing_time(t), divide_count(d) {}
bool operator<(const Node& other) const {
return passing_time > other.passing_time;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int, int>>> 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<Node> pq;
pq.push(Node(0, 0, 0));
vector<vector<vector<int>>> dp(N, vector<vector<int>>(K + 1, vector<int>(N, INT_MAX)));
while (!pq.empty()) {
Node curr = pq.top();
pq.pop();
if (curr.country == H) {
return curr.passing_time;
}
if (dp[curr.country][curr.divide_count][curr.passing_time] != INT_MAX) {
continue; // Already visited this state with a better passing time
}
dp[curr.country][curr.divide_count][curr.passing_time] = curr.passing_time;
for (auto& neighbor : graph[curr.country]) {
int next_country = neighbor.first;
int next_time = curr.passing_time + neighbor.second;
int next_divide_count = curr.divide_count;
if (arr[next_country] == 2 && next_divide_count < K) {
next_time /= 2;
next_divide_count++;
}
pq.push(Node(next_country, next_time, next_divide_count));
}
}
return -1; // Cannot reach Cyberland
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
352 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
135 ms |
240140 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
834 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
30 ms |
49608 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
102 ms |
171420 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
56656 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
740 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |