#include "cyberland.h"
#include <vector>
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
typedef long long ll;
const double MAX_DIST=1000000000000000000.0;
using namespace std;
int n,m,k,h;
vector<pair<int,double>>nodes[100000];
double dist[100000];
bool vis[100000];
void dfs(int node){
if(vis[node])
return;
vis[node]=true;
if(node==h)
return;
for(pair<int,double>ne:nodes[node]){
dfs(ne.first);
}
}
double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
n=N;
m=M;
k=K;
h=H;
for(int i=0;i<n;i++){
nodes[i].clear();
dist[i]=MAX_DIST;
vis[i]=false;
}
for(int i=0;i<m;i++){
nodes[x[i]].emplace_back(y[i],c[i]);
nodes[y[i]].emplace_back(x[i],c[i]);
}
dfs(0);
dist[0]=0;
queue<int>q;
q.push(0);
if(!vis[h])
return -1;
for(int i=0;i<n;i++){
if(arr[i]==0&&vis[i]){
dist[i]=0;
q.push(i);
}
}
while(!q.empty()){
int curr=q.front();
q.pop();
if(curr==h)
continue;
for(pair<int,double>ne:nodes[curr]){
double new_dist=dist[curr]+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
k=min(100,k);
while(k--){
for(int i=0;i<n;i++){
if(arr[i]==2&&vis[i]){
for(pair<int,double>ne:nodes[i]){
double new_dist=dist[i]/2.0+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
}
if(q.empty())
break;
while(!q.empty()){
int curr=q.front();
q.pop();
if(curr==h)
continue;
for(pair<int,double>ne:nodes[curr]){
double new_dist=dist[curr]+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
}
return dist[h];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2880 KB |
Correct. |
2 |
Correct |
14 ms |
3032 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3204 KB |
Correct. |
2 |
Correct |
22 ms |
3272 KB |
Correct. |
3 |
Correct |
18 ms |
3284 KB |
Correct. |
4 |
Correct |
20 ms |
3412 KB |
Correct. |
5 |
Correct |
19 ms |
3268 KB |
Correct. |
6 |
Correct |
16 ms |
4124 KB |
Correct. |
7 |
Correct |
21 ms |
4144 KB |
Correct. |
8 |
Correct |
10 ms |
4760 KB |
Correct. |
9 |
Correct |
18 ms |
3200 KB |
Correct. |
10 |
Correct |
18 ms |
3148 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3388 KB |
Correct. |
2 |
Correct |
18 ms |
3456 KB |
Correct. |
3 |
Correct |
17 ms |
3536 KB |
Correct. |
4 |
Correct |
21 ms |
3152 KB |
Correct. |
5 |
Correct |
19 ms |
3412 KB |
Correct. |
6 |
Correct |
5 ms |
3540 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8764 KB |
Correct. |
2 |
Correct |
22 ms |
3536 KB |
Correct. |
3 |
Correct |
20 ms |
3548 KB |
Correct. |
4 |
Correct |
20 ms |
3588 KB |
Correct. |
5 |
Correct |
22 ms |
3424 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
3480 KB |
Correct. |
2 |
Correct |
22 ms |
3484 KB |
Correct. |
3 |
Correct |
19 ms |
3352 KB |
Correct. |
4 |
Correct |
20 ms |
4556 KB |
Correct. |
5 |
Correct |
16 ms |
3204 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
3548 KB |
Correct. |
2 |
Correct |
17 ms |
3572 KB |
Correct. |
3 |
Correct |
34 ms |
10496 KB |
Correct. |
4 |
Correct |
13 ms |
4076 KB |
Correct. |
5 |
Correct |
20 ms |
3496 KB |
Correct. |
6 |
Correct |
18 ms |
3332 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3536 KB |
Correct. |
2 |
Correct |
4 ms |
3028 KB |
Correct. |
3 |
Correct |
60 ms |
12496 KB |
Correct. |
4 |
Correct |
56 ms |
5740 KB |
Correct. |
5 |
Correct |
55 ms |
10776 KB |
Correct. |
6 |
Correct |
38 ms |
9592 KB |
Correct. |
7 |
Incorrect |
49 ms |
5736 KB |
Wrong Answer. |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3400 KB |
Correct. |
2 |
Correct |
5 ms |
3028 KB |
Correct. |
3 |
Correct |
60 ms |
15136 KB |
Correct. |
4 |
Incorrect |
47 ms |
4236 KB |
Wrong Answer. |
5 |
Halted |
0 ms |
0 KB |
- |