제출 #976505

#제출 시각아이디문제언어결과실행 시간메모리
976505Marcus사이버랜드 (APIO23_cyberland)C++17
15 / 100
358 ms8784 KiB
#include <bits/stdc++.h> using namespace std; double const INF = 1e15; int const N = 1e5; vector<vector<pair<int, int>>> adj(N); vector<double> dist(N); vector<double> dist2(N); vector<bool> processed(N); priority_queue<pair<double, int>> q; double answer = INF; void dijkstra(int number, int target) { for (int j=0; j<number; j++) {processed[j] = false;} dist[0] = 0; for (int j = 0; j<number; j++) if (dist[j] < INF) q.push({-dist[j], j}); while (!q.empty()) { int a = q.top().second; q.pop(); if (processed[a]) continue; processed[a] = true; for (auto u : adj[a]) { int b = u.first, w = u.second; if (dist[a]+w < dist[b]) { dist[b] = dist[a]+w; q.push({-dist[b],b}); } } } answer = min(answer, dist[target]); } double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { answer = INF; for(int i = 0; i < n; i++) adj[i].clear(); for (int i=0; i<m; i++) { int v = x[i]; int u = y[i]; int w = c[i]; adj[v].push_back({u, w}); adj[u].push_back({v, w}); } for (int i=0; i<n; i++) {dist[i] = INF;} dijkstra(n, h); if (dist[h] == INF) {return -1;} for (int i=0; i<n; i++) {if (dist[i] != INF) dist[i] = (arr[i] ? INF : 0);} k = min(k, 65); for (int i=1; i<=k; i++) { dijkstra(n, h); for (int j=0; j<n; j++) {dist2[j] = INF;} for (int j=0; j<n; j++) { if (arr[j] == 2) { for (auto p: adj[j]) { int u = p.first; int w = p.second; dist2[u] = min(dist2[u], dist[j]/2+w); } } } for (int j=0; j<n; j++) {dist[j] = dist2[j];} } return answer; }
#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...