#include "cyberland.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
// struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
using lint=__int128_t;
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) {
vector<vector<pair<int,int>>> g(N);
rep(i,M){
g[x[i]].push_back({y[i],c[i]});
g[y[i]].push_back({x[i],c[i]});
}
vector<bool> flg(N);
{
stack<int> q;
q.push(0);
while(q.size()){
int p=q.top();q.pop();
flg[p]=1;
for(auto&&[e,c]:g[p]){
if(flg[e])continue;
q.push(e);
}
}
if(!flg[H]){
return -1;
}
}
K=min(K,50);
vector<vector<lint>> d(K+1,vector<lint>(N,lint(1)<<120));
pqmin<tuple<lint,int,int>> pq;
rep(i,N){
if(i==0||arr[i]==0){
d[0][i]=0;
pq.push({0,0,i});
}
}
while(pq.size()){
auto[cost,k,p]=pq.top();pq.pop();
if(d[k][p]<cost)continue;
for(auto&&[e,c]:g[p]){
lint nc=cost+(lint(c)<<k);
if(d[k][e]>nc){
d[k][e]=nc;
pq.push({nc,k,e});
}
if(arr[e]==2&&k<K){
if(d[k+1][e]>cost){
d[k+1][e]=cost;
pq.push({d[k][e],k+1,e});
}
}
}
}
double ans=1e18;
rep(i,K+1){
if(d[i][H]==(lint(1)<<120))continue;
long double t=(long double)(d[i][H])/(long double)(lint(1)<<i);
if(ans>t)ans=t;
}
if(ans>1e17)return -1;
else return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |