# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
977343 | Nexus | 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.
#define ll long long
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
const ll N=1e5+9;
pair<ll,ll>p;
ll vis[N],o[N],g;
vector<pair<ll,ll>>v[N];
priority_queue<pair<ll,ll>>q;
void dfs(ll node)
{
if(vis[i])return;
vis[node]=1;
if(!arr[i])o[i]=1;
for(auto i:v[node])dfs(i);
}
double solve(int n, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<ll>dis(n,1e18);
double ans=-1;
for(ll i=0;i<n;++i)
{
o[i]=0;
vis[i]=0,v[i].clear();
}
dfs(0);
for(ll i=0;i<n;++i)vis[i]=0;
for(ll i=0;i<M;++i)
{
v[x[i]].push_back({c[i],y[i]});
v[y[i]].push_back({c[i],x[i]});
}
dis[H]=0;
q.push({H,0});
while(q.size())
{
p=q.top();
g=p.second;
q.pop();
if(vis[g])continue;
vis[g]=1;
if(o[g])dis[0]=min(dis[0],dis[g]);
for(auto i:v[g])
{
if(dis[g]+i.first<dis[i.second])
{
dis[i.second]=dis[g]+i.first;
q.push({-dis[i.second],i.second});
}
}
}
if(dis[0]<1e18)ans=dis[0];
return ans;
}