Submission #1252610

#TimeUsernameProblemLanguageResultExecution timeMemory
1252610anfiCyberland (APIO23_cyberland)C++20
15 / 100
1022 ms2162688 KiB
#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-12) continue; for(auto &[v, w] : adj[u]){ double cost = c+w; if(dp[v][pos] > cost+1e-12){ dp[v][pos] = cost; pq.push({cost, v, pos}); } if(a[v] == 0){ if(dp[v][pos] > 0.0+1e-12){ 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-12){ 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...