# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1061417 | Muhammet | 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>
#include "cyberland.h"
#include "stub.cpp"
using namespace std;
#define ff first
#define ss second
vector <pair<int,int>> v[200005];
double v1[10][10];
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for(int i = 0; i <= n; i++){
v[i].clear();
}
for(int i = 0; i < m; i++){
v[x[i]].push_back({y[i],c[i]});
v[y[i]].push_back({x[i],c[i]});
}
if(n <= 3){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
v1[i][j] = -1;
}
}
for(int i = 0; i < m; i++){
v1[x[i]][y[i]] = c[i];
v1[y[i]][x[i]] = c[i];
}
int h1;
if(h == 1) h1 = 2;
else h1 = 1;
double ans = 1e9;
if(v1[0][h] != -1){
ans = min(ans,v1[0][h]);
}
if(v1[0][h1] != -1 and v1[h1][h] != -1){
if(arr[h1] == 0){
ans = min(ans, v1[h1][h]);
}
else if(arr[h1] == 2 and k > 0){
v1[0][h1] /= 2;
ans = min(ans, v1[0][h1] + v1[h1][h]);
}
}
return ans;
}
else {
vector <int> d(n,1e9);
d[0] = 0;
priority_queue <pair<int,int>> q;
q.push({0,0});
while(!q.empty()){
pair <int,int> w1 = q.top();
q.pop();
w1.ff *= (-1);
if(w1.ff != d[w1.ss]) continue;
for(auto i : v[w1.ss]){
if(d[i.ff] > d[w1.ss] + i.ss){
d[i.ff] = d[w1.ss] + i.ss;
q.push({-d[i.ff],i.ff});
}
}
}
if(d[h] == 1e9) d[h] = -1;
return d[h];
}
}