#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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)
{
vector<vector<pair<long long ,long long>>> adj(N);
for(long long i = 0 ; i < M ; i++)
{
adj[x[i]].push_back({y[i] , c[i]});
adj[y[i]].push_back({x[i] , c[i]});
}
priority_queue<pair<double , pair<long long ,long long>> , vector<pair<double , pair<long long ,long long>>> , greater<pair<double , pair<long long ,long long>>>> pq;
vector<vector<double>> dist(K + 1 , vector<double>(N , 1e16));
vector<vector<bool>> vis(K + 1 , vector<bool>(N , 0));
dist[K][0] = 0;
pq.push({0 , {K , 0}});
while(!pq.empty())
{
auto tp = pq.top();
pq.pop();
double d = tp.first ;
long long node = tp.second.second , k = tp.second.first;
if(vis[k][node])
continue;
vis[k][node] = 1;
for(auto [u , cost] : adj[node])
{
double nd = d + cost;
if(arr[u] == 0)
{
nd = 0;
}
if(nd < dist[k][u])
{
dist[k][u] = nd;
pq.push({nd , {k , u}});
}
if(arr[u] == 2 && k >= 1)
{
nd/=2.0;
if(nd < dist[k][u])
{
dist[k - 1][u] = nd;
pq.push({nd , {k - 1 , u}});
}
}
}
}
double mn = 1e16;
for(long long i = 0 ; i <= K ; i++)
{
mn= min(mn , dist[i][H]);
}
return mn;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
32 ms |
856 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1780 KB |
Correct. |
2 |
Correct |
22 ms |
1788 KB |
Correct. |
3 |
Correct |
26 ms |
1844 KB |
Correct. |
4 |
Correct |
21 ms |
1828 KB |
Correct. |
5 |
Correct |
22 ms |
1844 KB |
Correct. |
6 |
Correct |
20 ms |
4840 KB |
Correct. |
7 |
Correct |
27 ms |
4656 KB |
Correct. |
8 |
Correct |
12 ms |
7912 KB |
Correct. |
9 |
Correct |
23 ms |
1380 KB |
Correct. |
10 |
Correct |
23 ms |
1368 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
1732 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
181 ms |
22356 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
1724 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
1776 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
205 ms |
2348 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
796 ms |
2097152 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |