| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 777165 | groshi | 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"
#define int long long
using namespace std;
struct wi{
vector<int> Q;
double dp[203];
int co;
int odw=0;
}*w;
vector<int> moge;
void dfs(int x,int nie)
{
w[x].odw=1;
if(x==nie)
return;
if(w[x].co==0)
moge.push_back(x);
for(int i=0;i<w[x].Q.size();i+=2)
if(w[w[x].Q[i]].odw==0)
dfs(w[x].Q[i],nie);
}
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c, vector<int> arr)
{
w=new wi[n+3];
for(int i=0;i<m;i++)
{
w[x[i]].Q.push_back(y[i]);
w[y[i]].Q.push_back(x[i]);
w[x[i]].Q.push_back(c[i]);
w[y[i]].Q.push_back(c[i]);
}
for(int i=0;i<n;i++)
w[i].co=arr[i];
moge.clear();
dfs(0,h);
moge.push_back(0);
priority_queue<pair<double,pair<int,int> > > kolejka;
k=min(k,200LL);
for(int i=0;i<n;i++)
for(int j=0;j<=k;j++)
w[i].dp[j]=1e18;
for(int i=0;i<moge.size();i++)
kolejka.push({0.0,{moge[i],0}}),w[moge[i]].dp[0]=0;
while(!kolejka.empty())
{
auto para=kolejka.top();
kolejka.pop();
int x=para.second.first;
int typ=para.second.second;
double ile=para.first;
if(ile>w[x].dp[typ])
continue;
if(x==h)
continue;
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
double dodaj=w[x].Q[i+1];
if(w[pom].dp[typ]>ile+dodaj)
kolejka.push({ile+dodaj,{pom,typ}}),w[pom].dp[typ]=ile+dodaj;
if(w[pom].co!=2)
continue;
dodaj+=ile;
dodaj/=2;
if(w[pom].dp[typ+1]>dodaj && typ+1<=k)
kolejka.push({dodaj,{pom,typ+1}}),w[pom].dp[typ+1]=dodaj;
}
}
double minn=1e18;
for(int i=0;i<=k;i++)
minn=min(minn,w[h].dp[i]);
if(minn==1e18)
return -1;
else return minn;
}