#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;int m;int KK;int HH;
ll ar[200005];
ll xar[200005];ll yar[200005];ll car[200005];
vector<pair<int,ll>>e[200005];
void inp(){
// cin>>n>>m>>KK>>HH;
HH++;
for(int i=1;i<=n;i++){
// cin>>ar[i];
e[i].clear();
}
for(int i=1;i<=m;i++){
//cin>>xar[i]>>yar[i]>>car[i];
xar[i]++;yar[i]++;
e[xar[i]].push_back({yar[i],car[i]});
e[yar[i]].push_back({xar[i],car[i]});
}
}
int uf[200005];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}
double dis[110][100005];
int vis[110][100005];
double slv(){
for(int i=1;i<=n;i++){
uf[i]=i;
}
for(int i=1;i<=m;i++){
if(xar[i]==HH||yar[i]==HH){continue;}
mrg(xar[i],yar[i]);
}
/*
*/
priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>>pq;
KK=min(KK,70);
for(int k=0;k<=KK;k++){
for(int i=1;i<=n;i++){
dis[k][i]=1e16;
vis[k][i]=0;
}
}
dis[0][1]=0;
pq.push({0,{0,1}});
for(int i=2;i<=n;i++){
if(ar[i]==0&&fin(i)==fin(1)){
pq.push({0,{0,i}});
dis[0][i]=0;
}
}
for(int i=1;i<=m;i++){
mrg(xar[i],yar[i]);
}
if(fin(1)!=fin(HH)){
return -1;
}
while(pq.size()){
int nw=pq.top().second.second;
int nwk=pq.top().second.first;
pq.pop();
if(vis[nwk][nw]){continue;}
vis[nwk][nw]=1;
if(nw==HH){continue;}
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
ll w=e[nw][i].second;
if(vis[nwk][v]){continue;}
if(dis[nwk][v]>dis[nwk][nw]+w){
dis[nwk][v]=dis[nwk][nw]+w;
pq.push({dis[nwk][v],{nwk,v}});
}
}
}
for(int k=1;k<=KK;k++){
for(int i=1;i<=n;i++){
if(vis[k-1][i]&&ar[i]==2){
double vl=1e16;
for(int j=0;j<e[i].size();j++){
int v=e[i][j].first;
double w=e[i][j].second;
if(v==HH){continue;}
vl=min(vl,dis[k-1][v]+w);
}
dis[k][i]=vl/2.;
pq.push({dis[k][i],{k,i}});
}
}
while(pq.size()){
int nw=pq.top().second.second;
int nwk=pq.top().second.first;
pq.pop();
if(vis[nwk][nw]){continue;}
vis[nwk][nw]=1;
if(nw==HH){continue;}
for(int i=0;i<e[nw].size();i++){
int v=e[nw][i].first;
double w=e[nw][i].second;
if(vis[nwk][v]){continue;}
if(dis[nwk][v]>dis[nwk][nw]+w){
dis[nwk][v]=dis[nwk][nw]+w;
pq.push({dis[nwk][v],{nwk,v}});
}
}
}
}
double ans=dis[0][HH];
for(int i=1;i<=KK;i++){
if(!vis[i][HH]){continue;}
ans=min(ans,dis[i][HH]);
}
/*
for(int i=0;i<=3;i++){
for(int j=1;j<=n;j++){
cout<<dis[i][j]<<" ";
}cout<<endl;
}
*/
return ans;
}
//#define int int
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
/* cin>>N>>M>>K>>H;
for(int i=1;i<=N;i++){
int v;
cin>>v;
arr.push_back(v);
}
// cout<<M<<" ";
for(int i=1;i<=M;i++){
int a;int b;int cc;
cin>>a>>b>>cc;
x.push_back(a);y.push_back(b);c.push_back(cc);
// cout<<i<<" "<<M<<endl;
}
*/
n=N;m=M;KK=K;HH=H;
for(int i=0;i<x.size();i++){
xar[i+1]=x[i];
yar[i+1]=y[i];
car[i+1]=c[i];
}
for(int i=0;i<arr.size();i++){
ar[i+1]=arr[i];
}
// cout<<"hehe";
inp();
return slv();
}
/*
signed main()
{
cout<<fixed<<setprecision(7)<<solve(0,0,0,0,{},{},{},{});
// inp();
// cout<<slv();
return 0;
}
*/
Compilation message
cyberland.cpp: In function 'double slv()':
cyberland.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
cyberland.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int j=0;j<e[i].size();j++){
| ~^~~~~~~~~~~~
cyberland.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<e[nw].size();i++){
| ~^~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
cyberland.cpp:172:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i=0;i<arr.size();i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5500 KB |
Correct. |
2 |
Correct |
24 ms |
5460 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5952 KB |
Correct. |
2 |
Correct |
29 ms |
5844 KB |
Correct. |
3 |
Correct |
26 ms |
5864 KB |
Correct. |
4 |
Correct |
29 ms |
5912 KB |
Correct. |
5 |
Correct |
35 ms |
6028 KB |
Correct. |
6 |
Correct |
29 ms |
10192 KB |
Correct. |
7 |
Correct |
33 ms |
10060 KB |
Correct. |
8 |
Correct |
18 ms |
14792 KB |
Correct. |
9 |
Correct |
28 ms |
5460 KB |
Correct. |
10 |
Correct |
27 ms |
5472 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
5932 KB |
Correct. |
2 |
Correct |
28 ms |
5940 KB |
Correct. |
3 |
Correct |
29 ms |
5948 KB |
Correct. |
4 |
Correct |
29 ms |
5472 KB |
Correct. |
5 |
Correct |
29 ms |
5460 KB |
Correct. |
6 |
Correct |
9 ms |
9428 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
33840 KB |
Correct. |
2 |
Correct |
103 ms |
5876 KB |
Correct. |
3 |
Correct |
92 ms |
5896 KB |
Correct. |
4 |
Correct |
112 ms |
5968 KB |
Correct. |
5 |
Correct |
68 ms |
5456 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5996 KB |
Correct. |
2 |
Correct |
29 ms |
5972 KB |
Correct. |
3 |
Correct |
26 ms |
6024 KB |
Correct. |
4 |
Correct |
30 ms |
10524 KB |
Correct. |
5 |
Correct |
24 ms |
5476 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
6040 KB |
Correct. |
2 |
Correct |
23 ms |
6032 KB |
Correct. |
3 |
Correct |
60 ms |
42080 KB |
Correct. |
4 |
Correct |
22 ms |
9244 KB |
Correct. |
5 |
Correct |
28 ms |
5484 KB |
Correct. |
6 |
Correct |
25 ms |
5972 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
5960 KB |
Correct. |
2 |
Correct |
21 ms |
6356 KB |
Correct. |
3 |
Correct |
491 ms |
36784 KB |
Correct. |
4 |
Correct |
264 ms |
14100 KB |
Correct. |
5 |
Correct |
434 ms |
27460 KB |
Correct. |
6 |
Correct |
187 ms |
16972 KB |
Correct. |
7 |
Correct |
272 ms |
14252 KB |
Correct. |
8 |
Correct |
204 ms |
7048 KB |
Correct. |
9 |
Correct |
90 ms |
5972 KB |
Correct. |
10 |
Correct |
83 ms |
5964 KB |
Correct. |
11 |
Correct |
190 ms |
6500 KB |
Correct. |
12 |
Correct |
102 ms |
5964 KB |
Correct. |
13 |
Correct |
103 ms |
6040 KB |
Correct. |
14 |
Correct |
265 ms |
18128 KB |
Correct. |
15 |
Correct |
229 ms |
9552 KB |
Correct. |
16 |
Correct |
95 ms |
5992 KB |
Correct. |
17 |
Correct |
110 ms |
5992 KB |
Correct. |
18 |
Correct |
99 ms |
6020 KB |
Correct. |
19 |
Correct |
258 ms |
5972 KB |
Correct. |
20 |
Correct |
8 ms |
5460 KB |
Correct. |
21 |
Correct |
9 ms |
5844 KB |
Correct. |
22 |
Correct |
17 ms |
6612 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
6876 KB |
Correct. |
2 |
Correct |
38 ms |
7460 KB |
Correct. |
3 |
Correct |
276 ms |
101076 KB |
Correct. |
4 |
Correct |
288 ms |
10508 KB |
Correct. |
5 |
Correct |
1002 ms |
44488 KB |
Correct. |
6 |
Correct |
401 ms |
22312 KB |
Correct. |
7 |
Correct |
510 ms |
27104 KB |
Correct. |
8 |
Correct |
259 ms |
7244 KB |
Correct. |
9 |
Correct |
170 ms |
6860 KB |
Correct. |
10 |
Correct |
144 ms |
6916 KB |
Correct. |
11 |
Correct |
158 ms |
5952 KB |
Correct. |
12 |
Correct |
195 ms |
6904 KB |
Correct. |
13 |
Correct |
183 ms |
6896 KB |
Correct. |
14 |
Correct |
1189 ms |
45124 KB |
Correct. |
15 |
Correct |
915 ms |
52940 KB |
Correct. |
16 |
Correct |
437 ms |
22168 KB |
Correct. |
17 |
Correct |
287 ms |
9328 KB |
Correct. |
18 |
Correct |
164 ms |
6852 KB |
Correct. |
19 |
Correct |
218 ms |
6916 KB |
Correct. |
20 |
Correct |
189 ms |
6940 KB |
Correct. |
21 |
Correct |
514 ms |
6820 KB |
Correct. |
22 |
Correct |
12 ms |
5844 KB |
Correct. |
23 |
Correct |
15 ms |
6660 KB |
Correct. |
24 |
Correct |
33 ms |
7420 KB |
Correct. |