#include "cyberland.h"
#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;
const int N=1e5+10;
const long long inf=1e16;
int n,arr[N];
vector<pair<int,long long>> adj[N];
long long dist[N],MS=-1;
long long dyk(int s,int e)
{
for(int j=0;j<n;j++)
dist[j]=inf;
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
dist[s]=0;
pq.push({0,s});
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==e) // this is cz we dont go other side of h
continue;
if(tp.first==dist[tp.second])
{
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});
}
}
}
}
// cout<<"DY from "<<s<<endl;
// for(int pp=0;pp<n;pp++)
// {
// cout<<dist[pp]<<' ';
// }
// cout<<endl;
return ((dist[e]==inf)?MS:dist[e]);
}
long long dyk_comb(int e)
{
dyk(0,e);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
for(int j=0;j<n;j++)
{
if(dist[j]!=inf and (j==0 or arr[j]==0))
{
dist[j]=0;
pq.push({0,j});
}
else
dist[j]=inf;
}
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.first==dist[tp.second])
{
if(tp.second==e)
{
continue;
}
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 ((dist[e]==inf)?MS:dist[e]);
}
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();
}
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 |
519 ms |
3508 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
3416 KB |
Correct. |
2 |
Correct |
28 ms |
3588 KB |
Correct. |
3 |
Correct |
27 ms |
3416 KB |
Correct. |
4 |
Correct |
27 ms |
3612 KB |
Correct. |
5 |
Correct |
28 ms |
3716 KB |
Correct. |
6 |
Correct |
23 ms |
4444 KB |
Correct. |
7 |
Correct |
29 ms |
4444 KB |
Correct. |
8 |
Correct |
12 ms |
5212 KB |
Correct. |
9 |
Correct |
79 ms |
3668 KB |
Correct. |
10 |
Correct |
69 ms |
3444 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
3420 KB |
Correct. |
2 |
Correct |
30 ms |
4436 KB |
Correct. |
3 |
Correct |
27 ms |
3924 KB |
Correct. |
4 |
Correct |
73 ms |
4340 KB |
Correct. |
5 |
Correct |
73 ms |
4336 KB |
Correct. |
6 |
Correct |
6 ms |
4440 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
8532 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3672 KB |
Correct. |
2 |
Correct |
25 ms |
3676 KB |
Correct. |
3 |
Correct |
27 ms |
3700 KB |
Correct. |
4 |
Correct |
21 ms |
4700 KB |
Correct. |
5 |
Correct |
69 ms |
3420 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
3672 KB |
Correct. |
2 |
Correct |
23 ms |
4432 KB |
Correct. |
3 |
Correct |
33 ms |
12116 KB |
Correct. |
4 |
Correct |
15 ms |
4956 KB |
Correct. |
5 |
Correct |
69 ms |
4296 KB |
Correct. |
6 |
Correct |
26 ms |
4700 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
3676 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
28 ms |
3684 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |