#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e30;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
double ans = 1e30;
vector<pair<int,int>> adj[N];
vector<vector<double>> dp(N, vector<double>(K+1, inf));
for(int i = 0;i < M; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector<int> a = arr;
priority_queue<tuple<double,int,int>, vector<tuple<double, int, int>>, greater<tuple<double,int,int>>> pq;
dp[0][0] = 0.0;
pq.push({0.0, 0,0});
while(!pq.empty()){
auto [c, u, pos] = pq.top(); pq.pop();
if(c > dp[u][pos]+1e-9) continue;
for(auto &[v, w] : adj[u]){
double cost = c+w;
if(dp[v][pos] > cost+1e-9){
dp[v][pos] = cost;
pq.push({cost, v, pos});
}
if(a[v] == 0){
if(dp[v][pos] > 0.0+1e-9){
dp[v][pos] = 0.0;
pq.push({0.0, v, pos});
}
}
if(a[v] == 2 && pos < K){
double co = (c+w)/2.0;
if(dp[v][pos+1] > co+1e-9){
dp[v][pos+1] = co;
pq.push({co, v, pos+1});
}
}
}
}
for(int i = 0; i <= K; i++) ans = min(ans, dp[H][i]);
return (ans >= inf/2 ? -1.0 : ans);
}
/*
signed main(){
int n,m; cin >> n >> m;
vector<pair<int,int>> adj[n+3];
vector<vector<int>> dp(n+3, vector<int>(2, mod));
dp[1][0] = 0;
for(int i = 0,u,v,c; i < m; i++){
cin >> u >> v >> c;
adj[u].push_back({v, c});
}
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
pq.push({0, 1, 0});
while(!pq.empty()){
auto [c, u, cek] = pq.top(); pq.pop();
if(dp[u][cek] < c) continue;
for(auto &[v, w] : adj[u]){
if(dp[v][cek] > c+w){
dp[v][cek] = c+w;
pq.push({dp[v][cek], v,cek});
}
if(cek == 0){
int dc = w/2;
if(dp[v][1] > dc+c){
dp[v][1] = dc+c;
pq.push({dp[v][1], v, 1});
}
}
}
}
cout << dp[n][1];
}*/
# | 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... |