제출 #756666

#제출 시각아이디문제언어결과실행 시간메모리
756666vioalbert사이버랜드 (APIO23_cyberland)C++17
8 / 100
229 ms7820 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const double INF = 1e15; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector adj(N, vector<pair<int, int>>()); for(int i = 0; i < M; i++) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } const auto dijkstra = [&](const vector<int> &sources, vector<double> &dist) { using state = pair<double, int>; // dist, node vector<int> vis(N, 0); priority_queue<state, vector<state>, greater<state>> pq; for(int i : sources) pq.push({dist[i], i}); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; for(auto [v, c] : adj[u]) { if(dist[v] > dist[u] + c) { pq.push({dist[v] = dist[u] + c, v}); } } } }; vector<int> sources{0}; for(int i = 1; i < N; i++) if(arr[i] == 0) sources.push_back(i); vector<double> dist(N, INF); for(int i : sources) dist[i] = 0.0; double ans = INF; for(int it = 0; it < min(K, 95); it++) { if(it == 1) { sources.clear(); for(int i = 0; i < N; i++) if(arr[i] != 1) sources.push_back(i); } dijkstra(sources, dist); ans = min(ans, dist[H]); } return 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...