#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,arr[N];
double eps=1/(1e9);
vector<pair<int,double>> adj[N];
double dist[N];
double dyk(int s,int e)
{
for(int j=0;j<n;j++)
dist[j]=1e14+1;
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
dist[s]=0;
pq.push({0,s});
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==e)
return tp.first;
if((tp.first-dist[tp.second])<=eps)
{
int v=tp.second;
for(auto [u,w]:adj[v])
{
if((dist[v]+w)<dist[u])
{
dist[u]=dist[v]+w;
pq.push({dist[u],u});
}
}
}
}
return -1;
}
double dyk_comb(int e)
{
dyk(0,e);
vector<int> acd;
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
for(int j=0;j<n;j++)
{
if(dist[j]<(1e14+1) and arr[j]==0)
{
acd.push_back(j);
dist[j]=0;
pq.push({0,j});
}
else
dist[j]=1e14+1;
}
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==e)
return tp.first;
if((tp.first-dist[tp.second])<=eps)
{
int v=tp.second;
for(auto [u,w]:adj[v])
{
if((dist[v]+w)<dist[u])
{
dist[u]=dist[v]+w;
pq.push({dist[u],u});
}
}
}
}
return -1;
}
double solve(int NP, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> AS) {
n=NP;
// DONT FORGET TO CLEAR THE THINGS YOU USED
for(int i=0;i<n;i++)
{
arr[i]=AS[i];
adj[i].clear();
}
arr[0]=0;
bool all_one=1;
for(auto i:arr)
all_one&=(i==1);
for(int j=0;j<m;j++)
{
adj[x[j]].push_back({y[j],c[j]});
adj[y[j]].push_back({x[j],c[j]});
}
if(all_one)
{
return dyk(0,h);
}
else{
return dyk_comb(h);
}
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
664 ms |
3404 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3616 KB |
Correct. |
2 |
Correct |
27 ms |
4444 KB |
Correct. |
3 |
Correct |
27 ms |
4440 KB |
Correct. |
4 |
Correct |
27 ms |
4444 KB |
Correct. |
5 |
Correct |
34 ms |
4444 KB |
Correct. |
6 |
Correct |
17 ms |
5128 KB |
Correct. |
7 |
Correct |
24 ms |
5468 KB |
Correct. |
8 |
Correct |
12 ms |
5720 KB |
Correct. |
9 |
Correct |
84 ms |
4180 KB |
Correct. |
10 |
Correct |
84 ms |
4200 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
3416 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
8504 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3688 KB |
Correct. |
2 |
Correct |
26 ms |
4696 KB |
Correct. |
3 |
Correct |
25 ms |
4700 KB |
Correct. |
4 |
Correct |
21 ms |
5724 KB |
Correct. |
5 |
Correct |
84 ms |
4176 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
3672 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
3672 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
26 ms |
3672 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |