Submission #1253922

#TimeUsernameProblemLanguageResultExecution timeMemory
1253922anfi사이버랜드 (APIO23_cyberland)C++20
0 / 100
17 ms7232 KiB
#include<bits/stdc++.h> using namespace std; const double INF = 1e8; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) { k = min(k, 100); vector<vector<pair<int, double>>> 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<double> dist(n, INF), temp(n, INF); priority_queue<pair<double, int>> pq; for(auto &p : temp) p = INF; for(auto i = 0; i < k; i++) { pq.push({0, i}); temp[i] = 0.; } while(!pq.empty()) { auto [cur, u] = pq.top(); pq.pop(); if(cur != -dist[u]) continue; for(auto [v, w] : adj[u]) { if(temp[v] > cur + w) { temp[v] = cur + w; pq.push({-temp[v], v}); } } } double ans = INF; for(auto &p : temp) p = INF; for(auto i = 0; i < k; i++) { pq.push({0, i}); temp[i] = 0.; } while(!pq.empty()) { auto [cur, u] = pq.top(); pq.pop(); if(cur != -dist[u]) continue; for(auto [v, w] : adj[u]) { if(temp[v] > cur + w) { temp[v] = cur + w; pq.push({-temp[v], v}); } } } ans = min(ans, temp[h]); return ans < INF ? ans : -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...