#include "cyberland.h"
#include <vector>
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
typedef long long ll;
typedef double lld;
const lld MAX_DIST=10000000000000000000000000.0;
using namespace std;
int n,m,k,h;
vector<pair<int,lld>>nodes[100000];
lld dist[100000];
lld old_dist[100000];
bool vis[100000];
void dfs(int node){
if(vis[node])
return;
vis[node]=true;
if(node==h)
return;
for(pair<int,lld>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);
}
}
k++;
k=min(100,k);
while(k--){
while(!q.empty()){
int curr=q.front();
q.pop();
if(curr==h)
continue;
for(pair<int,lld>ne:nodes[curr]){
lld new_dist=dist[curr]+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
for(int i=0;i<n;i++)
old_dist[i]=dist[i];
for(int i=0;i<n;i++){
if(arr[i]==2&&vis[i]){
for(pair<int,lld>ne:nodes[i]){
lld new_dist=old_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;
}
return dist[h];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
2900 KB |
Correct. |
2 |
Correct |
21 ms |
3060 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
3220 KB |
Correct. |
2 |
Correct |
18 ms |
3704 KB |
Correct. |
3 |
Correct |
19 ms |
3672 KB |
Correct. |
4 |
Correct |
18 ms |
3708 KB |
Correct. |
5 |
Correct |
19 ms |
3828 KB |
Correct. |
6 |
Correct |
17 ms |
4532 KB |
Correct. |
7 |
Correct |
29 ms |
4584 KB |
Correct. |
8 |
Correct |
10 ms |
4976 KB |
Correct. |
9 |
Correct |
18 ms |
3448 KB |
Correct. |
10 |
Correct |
27 ms |
3404 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
3696 KB |
Correct. |
2 |
Correct |
21 ms |
3660 KB |
Correct. |
3 |
Correct |
17 ms |
3684 KB |
Correct. |
4 |
Correct |
19 ms |
2992 KB |
Correct. |
5 |
Correct |
19 ms |
3536 KB |
Correct. |
6 |
Correct |
6 ms |
3528 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
9656 KB |
Correct. |
2 |
Correct |
21 ms |
3616 KB |
Correct. |
3 |
Correct |
19 ms |
3728 KB |
Correct. |
4 |
Correct |
20 ms |
3668 KB |
Correct. |
5 |
Correct |
20 ms |
3512 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3796 KB |
Correct. |
2 |
Correct |
21 ms |
3872 KB |
Correct. |
3 |
Correct |
18 ms |
3844 KB |
Correct. |
4 |
Correct |
19 ms |
5128 KB |
Correct. |
5 |
Correct |
18 ms |
3440 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3684 KB |
Correct. |
2 |
Correct |
16 ms |
3616 KB |
Correct. |
3 |
Correct |
34 ms |
11212 KB |
Correct. |
4 |
Correct |
13 ms |
4344 KB |
Correct. |
5 |
Correct |
18 ms |
3572 KB |
Correct. |
6 |
Correct |
18 ms |
3504 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3820 KB |
Correct. |
2 |
Correct |
5 ms |
3060 KB |
Correct. |
3 |
Incorrect |
67 ms |
14532 KB |
Wrong Answer. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
3572 KB |
Correct. |
2 |
Correct |
5 ms |
3080 KB |
Correct. |
3 |
Correct |
75 ms |
17652 KB |
Correct. |
4 |
Incorrect |
47 ms |
5708 KB |
Wrong Answer. |
5 |
Halted |
0 ms |
0 KB |
- |