| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1262364 | PlayVoltz | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include "cyberland_apio23.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int, int>
#define pdi pair<double, int>
#define mp make_pair
const int INF = LLONG_MAX;
double solve(int32_t n, int32_t m, int32_t K, int32_t h, vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, vector<int32_t> arr){
K = min(K, 70);
vector<vector<pii> > graph(n);
vector<vector<long double> > dj(n, vector<long double>(K+1, INF));
priority_queue<pdi, vector<pdi>, greater<pdi> > pq;
for (int i=0; i<m; ++i){
graph[x[i]].pb(mp(y[i], c[i]));
graph[y[i]].pb(mp(x[i], c[i]));
}
dj[0][0]=0;
for (int k=0; k<=K; ++k){
for (int i=0; i<n; ++i)if (dj[i][k]!=INF)pq.push(mp(dj[i][k], i));
while (!pq.empty()){
int cnode = pq.top().second;
long double dist = pq.top().first;
pq.pop();
if (abs(dist-dj[cnode][k])>1e-9 || cnode==h)continue;
for (auto num:graph[cnode]){
if (!arr[num.first] && dj[num.first][k]>0){
dj[num.first][k]=0;
pq.push(mp(0, num.first));
continue;
}
if (dist+num.second<dj[num.first][k]){
dj[num.first][k]=dist+num.second;
pq.push(mp(dj[num.first][k], num.first));
}
if (arr[cnode]==2 && k<K && dj[num.first][k+1]>dist/2+num.second)dj[num.first][k+1]=dist/2+num.second;
}
}
}
long double minnum=INF;
for (int i=0; i<=K; ++i)minnum=min(minnum, dj[h][i]);
return (minnum==INF?-1:minnum);
}