#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
double eps=1/(1e9);
vector<pair<int,double>> adj[N];
double dist[N];
double bef[N];
double save[N];
bool vis[N];
int spe[N],par[N];
double dyk(int s,int e,int ing=-1)
{
for(int j=0;j<n;j++)
{
par[j]=-1;
bef[j]=dist[j]=1e14+1;
}
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
dist[s]=0;
pq.push({dist[s],s});
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==ing)
continue;
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(par[v]==u)
continue;
if((dist[v]+w)<dist[u])
{
par[u]=v;
dist[u]=dist[v]+w;
bef[u]=min(bef[u],dist[u]);
if(spe[u]==0)
dist[u]=0;
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> arr) {
n=NP;
// DONT FORGET TO CLEAR THE THINGS YOU USED
for(int i=0;i<n;i++)
{
adj[i].clear();
spe[i]=arr[i];
}
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]});
}
bool two=0;
for(auto i:arr)
two|=(i==2);
if(all_one)
{
return dyk(0,h);
}
else if(!two)
{
dyk(h,-1);
for(int i=0;i<n;i++)
save[i]=bef[i];
dyk(0,-1,h);
double mn=2e14;
for(int i=0;i<n;i++)
mn=min(mn,dist[i]+save[i]);
if(arr[h]==0)
mn=0;
return mn;
}
return -1;
}
Compilation message
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:84:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
84 | if(arr[h]==0)
| ^~
cyberland.cpp:86:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
86 | return mn;
| ^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
14 ms |
5976 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
5976 KB |
Correct. |
2 |
Correct |
19 ms |
6232 KB |
Correct. |
3 |
Correct |
18 ms |
5980 KB |
Correct. |
4 |
Correct |
19 ms |
5980 KB |
Correct. |
5 |
Correct |
19 ms |
5980 KB |
Correct. |
6 |
Correct |
15 ms |
6672 KB |
Correct. |
7 |
Correct |
21 ms |
6748 KB |
Correct. |
8 |
Correct |
10 ms |
7516 KB |
Correct. |
9 |
Correct |
18 ms |
6164 KB |
Correct. |
10 |
Correct |
17 ms |
5724 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
24 ms |
5980 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
10320 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
6124 KB |
Correct. |
2 |
Correct |
18 ms |
5976 KB |
Correct. |
3 |
Correct |
18 ms |
5976 KB |
Correct. |
4 |
Correct |
18 ms |
7004 KB |
Correct. |
5 |
Correct |
16 ms |
5916 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
6176 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
15 ms |
5976 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
15 ms |
6232 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |