#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int N=1e5;
const double INF=1e16;
vector<pair<int,int>> v[N+1];
priority_queue<array<double,4>, vector<array<double,4>>, greater<array<double,4>>> pq;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a){
for(int i=0; i<n; i++) v[i].clear();
for(int i=0; i<m; i++){
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({x[i], c[i]});
}
k=min(k, 70);
// set<int> t;
// vector<bool> vis(n);
// queue<int> q;
// q.push(0);
// vis[0]=true;
// while(!q.empty()){
// int u=q.front(); q.pop();
// if(u==h) continue;
// for(auto [p, q1]:v[u]){
// if(vis[p]) continue;
// if(a[p]==0) t.insert(p);
// q.push(p);
// vis[p]=true;
// }
// }
double pw[k+1];
pw[0]=1.0;
for(int i=1; i<=k; i++) pw[i]=pw[i-1]*2;
vector<vector<double>> dp(n, vector<double>(k+1, INF));
for(int i=0; i<=k; i++) dp[h][i]=0;
pq.push({0, h, 0, 0});
double ans=INF;
while(!pq.empty()){
double d=pq.top()[0];
int u=pq.top()[1], dis=pq.top()[2], nol=pq.top()[3];
pq.pop();
if(d>dp[u][dis]) continue;
for(auto [to, dist]:v[u]){
if(nol && d<dp[to][dis]){
dp[to][dis]=d;
pq.push({dp[to][dis], to, dis, nol});
}
if(d+dist/pw[dis]<dp[to][dis]){
dp[to][dis]=d+dist/pw[dis];
pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[u]==0)});
}
}
}
for(int i=0; i<=k; i++) ans=min(ans, dp[0][i]);
if(ans==INF) return -1;
return ans;
}
/*
int main(){
fast();
int n, m, k, h; cin>>n>>m>>k>>h;
vector<int> x(N+1), y(N+1), c(N+1), a(N+1);
for(int i=0; i<m; i++){
cin>>x[i]>>y[i]>>c[i];
}
for(int i=0; i<n; i++) cin>>a[i];
cout<<solve(n, m, k, h, x, y, c, a);
}
*/
/*
const int N=1e5;
const double INF=1e16;
int n, m, k, h;
vector<pair<int,int>> v[N+1], ad; //adventure graph
vector<int> a;
bool f=false; //find cyberland
void dfs(int node, int p){
if(f) return;
for(auto [i, d]:v[node]){
if(i==p) continue;
int di=0;
if(a[i]!=0) di=d;
ad.push_back({di, a[i]});
if(i==h) f=true;
dfs(i, node);
}
if(f) return;
ad.pop_back();
}
priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>>> pq;
double solve(int nn, int mm, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> aa){
for(int i=0; i<n; i++) v[i].clear();
n=nn, m=mm, k=kk, h=hh, a=aa;
for(int i=0; i<m; i++){
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({x[i], c[i]});
}
// if(m==n-1){
// ad.clear();
// dfs(0, -1);
// priority_queue<int> pqq;
// double ans=0;
// for(auto [p, q]:ad){
// if(q==2) pqq.push(p);
// else ans+=p;
// }
// while(!pqq.empty()){
// int u=pqq.top(); pqq.pop();
// if(k) ans+=double(u)/2;
// else ans+=u;
// k--;
// }
// return ans;
// }
vector<vector<double>> dp(n+1, vector<double>(k+1, INF));
dp[0][0]=0;
pq.push({0, 0, 0}); //dist, node now, disc
while(!pq.empty()){
auto[d, u, dis]=pq.top(); pq.pop();
if(d>dp[u][dis]) continue;
for(auto [to, dist]:v[u]){
if(a[to]==0){
if(0<dp[to][dis]){
dp[to][dis]=0;
pq.push({0, to, dis});
}
}
else if(a[to]==1){
if(d+dist<dp[to][dis]){
dp[to][dis]=d+dist;
pq.push({dp[to][dis], to, dis});
}
}
else{
if(d+dist<dp[to][dis]){
dp[to][dis]=d+dist;
pq.push({dp[to][dis], to, dis});
}
if(dis<k && d+dist/2<dp[to][dis+1]){
dp[to][dis+1]=d+dist/2;
pq.push({dp[to][dis+1], to, dis+1});
}
}
}
}
double ans=INF;
for(int i=0; i<=k; i++) ans=min(ans, dp[h][i]);
if(ans==INF) return -1;
else return ans;
}
*/
/*
int main(){
fast();
int n, m, k, h; cin>>n>>m>>k>>h;
vector<int> x(N+1), y(N+1), c(N+1), a(N+1);
for(int i=0; i<m; i++){
cin>>x[i]>>y[i]>>c[i];
}
for(int i=0; i<n; i++) cin>>a[i];
cout<<solve(n, m, k, h, x, y, c, a);
}
*/
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:36:14: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
36 | pq.push({0, h, 0, 0});
| ^
cyberland.cpp:46:27: warning: narrowing conversion of 'to' from 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} to 'double' [-Wnarrowing]
46 | pq.push({dp[to][dis], to, dis, nol});
| ^~
cyberland.cpp:46:31: warning: narrowing conversion of 'dis' from 'int' to 'double' [-Wnarrowing]
46 | pq.push({dp[to][dis], to, dis, nol});
| ^~~
cyberland.cpp:46:36: warning: narrowing conversion of 'nol' from 'int' to 'double' [-Wnarrowing]
46 | pq.push({dp[to][dis], to, dis, nol});
| ^~~
cyberland.cpp:50:27: warning: narrowing conversion of 'to' from 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} to 'double' [-Wnarrowing]
50 | pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[u]==0)});
| ^~
cyberland.cpp:50:35: warning: narrowing conversion of '(dis + ((int)((dis < k) && (a.std::vector<int>::operator[](((std::vector<int>::size_type)to)) == 2))))' from 'int' to 'double' [-Wnarrowing]
50 | pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[u]==0)});
| ~~~~^~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:50:61: warning: narrowing conversion of '(nol | (a.std::vector<int>::operator[](((std::vector<int>::size_type)u)) == 0))' from 'int' to 'double' [-Wnarrowing]
50 | pq.push({dp[to][dis], to, (dis+(dis<k && a[to]==2)), nol|(a[u]==0)});
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2772 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
3028 KB |
Correct. |
| 2 |
Correct |
24 ms |
3000 KB |
Correct. |
| 3 |
Correct |
23 ms |
3028 KB |
Correct. |
| 4 |
Correct |
23 ms |
2988 KB |
Correct. |
| 5 |
Correct |
23 ms |
3068 KB |
Correct. |
| 6 |
Correct |
21 ms |
6040 KB |
Correct. |
| 7 |
Correct |
27 ms |
5992 KB |
Correct. |
| 8 |
Correct |
14 ms |
9556 KB |
Correct. |
| 9 |
Correct |
23 ms |
2772 KB |
Correct. |
| 10 |
Correct |
23 ms |
2772 KB |
Correct. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
3028 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
22204 KB |
Correct. |
| 2 |
Incorrect |
29 ms |
3028 KB |
Wrong Answer. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
3096 KB |
Correct. |
| 2 |
Correct |
23 ms |
3104 KB |
Correct. |
| 3 |
Correct |
21 ms |
3056 KB |
Correct. |
| 4 |
Correct |
24 ms |
6052 KB |
Correct. |
| 5 |
Correct |
21 ms |
2644 KB |
Correct. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
3128 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
3112 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
3520 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
