Submission #1253921

#TimeUsernameProblemLanguageResultExecution timeMemory
1253921anfiCyberland (APIO23_cyberland)C++20
15 / 100
447 ms21404 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second const double INF = 1e18; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){ K = min(K, 100); // batasi K agar tidak terlalu besar vector<vector<pair<int,int>>> adj(N); 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<vector<double>> dist(N, vector<double>(K+1, INF)); priority_queue<pair<double, pair<int,int>>, vector<pair<double,pair<int,int>>>, greater<>> pq; dist[0][K] = 0.0; pq.push({0.0, {0, K}}); while(!pq.empty()){ auto [d, state] = pq.top(); pq.pop(); int u = state.fi; int k = state.se; if(d > dist[u][k]) continue; for(auto &[v, w] : adj[u]){ if(dist[v][k] > d + w){ dist[v][k] = d + w; pq.push({dist[v][k], {v, k}}); } if(arr[u] == 2 && k > 0){ double nd = d + w / 2.0; if(dist[v][k-1] > nd){ dist[v][k-1] = nd; pq.push({nd, {v, k-1}}); } } } } double ans = *min_element(dist[H].begin(), dist[H].end()); return (ans >= INF/2 ? -1.0 : ans); }
#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...