| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 878663 | hello_there_123 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#include "cyberland.h"
double solve(int N, int M, int K, int end, std::vector<int> x, std::vector<int> y, std::vector<int> z, std::vector<int> arr) {
vector<pair<int,int> >v[N+3]; //node, val
for(int i=0;i<M;i++){
v[x[i]].push_back(make_pair(y[i],z[i]));
v[y[i]].push_back(make_pair(x[i],z[i]));
}
priority_queue<pair<double, pair<int,int> >, vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > pq;
//val, node, k
double dist[N+3][K+3];
bool vis[N+3];f
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(0);
vis[0] = 1;
while(!q.empty()){
int no = q.front();
q.pop();
for(auto p:v[no]){
if(!vis[p.first])q.push(p.first);
vis[p.first] = 1;
}
}
for(int i=0;i<N;i++){
if(vis[i] == 1 && (arr[i] == 0 || i==0)){
pq.push(mp(0,mp(i,0)));
for(int j=0;j<=K;j++) dist[i][j] = 0;
}
else for(int j=0;j<=K;j++) dist[i][j] = -1;
}
while(!pq.empty()){
double val = pq.top().first;
int no = pq.top().second.first;
int k = pq.top().second.second;
pq.pop();
if(no == end) continue;
for(auto p: v[no]){
if(dist[p.first][k] == -1 || dist[p.first][k] > val + (double) p.second){
dist[p.first][k] = val+(double)p.second;
pq.push(mp(val+(double)p.second,mp(p.first,k)));
}
if(k == K || arr[p.first]!=2) continue;
if(dist[p.first][k+1] == -1 || dist[p.first][k+1] > (val+(double)p.second)/2){
dist[p.first][k+1] = (val+(double)p.second)/2;
pq.push(mp((val+(double)p.second)/2, mp(p.first,k+1)));
}
}
}
double ans = 1e15;
for(int i=0;i<=K;i++){
if(dist[end][i]!=-1) ans = min(ans, dist[end][i]);
}
if(ans != 1e15) return ans;
else return -1;
}