제출 #968514

#제출 시각아이디문제언어결과실행 시간메모리
968514saayan007사이버랜드 (APIO23_cyberland)C++17
44 / 100
36 ms11836 KiB
#include "bits/stdc++.h" #include "cyberland.h" using namespace std; #include <vector> void bfs(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr, vector<pair<int, double>> adj[], double dist[]) { bool vis[N] = {}; queue<int> qu; vis[0] = 1; qu.push(0); dist[0] = 0; while(!qu.empty()) { int a = qu.front(); qu.pop(); if(a == H) continue; for(auto [b, w] : adj[a]) { if(vis[b]) continue; vis[b] = 1; qu.push(b); if(arr[b] == 0) dist[b] = 0; } } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<pair<int, double>> adj[N]; 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]); } double dist[N]; for(int i = 0; i < N; ++i) dist[i] = -1; bfs(N, M, K, H, x, y, c, arr, adj, dist); priority_queue<pair<double, int>> pq; for(int i = 0; i < N; ++i) { if(dist[i] == 0 || i == 0) { dist[i] = 0; pq.emplace(-dist[i], i); } } while(!pq.empty()) { int a = pq.top().second; double d = -pq.top().first; pq.pop(); if(dist[a] < d || a == H) { continue; } for(auto [b, w] : adj[a]) { if(dist[b] == -1 || d + w < dist[b]) { dist[b] = d + w; pq.emplace(-dist[b], b); } } } return dist[H]; }
#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...