제출 #976031

#제출 시각아이디문제언어결과실행 시간메모리
976031nnin사이버랜드 (APIO23_cyberland)C++17
97 / 100
3037 ms15432 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define pid pair<int,double> #define f first #define s second #define A pair<double, int> vector<pid> adj[100005]; bool reach[100005]; int HH, N; void dfs(int u) { reach[u] = 1; if(u==HH) return; for(auto [v, w]:adj[u]) { if(!reach[v]) dfs(v); } } double mindis[100005]; void dij(vector<int> &arr) { priority_queue<A, vector<A>, greater<A>> pq; for(int i=0;i<N;i++) { if(reach[i] && mindis[i]<1e18) pq.push({mindis[i], i}); } vector<bool> vis(N, 0); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; if(u==HH) continue; for(auto [v, w]:adj[u]) { if(reach[v] && mindis[v]>mindis[u]+w) { mindis[v] = mindis[u]+w; pq.push({mindis[v], v}); } } } vector<pid> tmp; for(int u=0;u<N;u++) { double mn = mindis[u]; if(reach[u] && arr[u]==2) { for(auto [v, w]:adj[u]) { if(reach[v] && v!=HH) mn = min(mn, (mindis[v]+w)/2.0); } } if(mn<mindis[u]) tmp.push_back({u, mn}); } for(auto [u, dis]:tmp) { mindis[u] = min(mindis[u], dis); } } double solve(int NN, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { HH = H; N = NN; for(int i=0;i<N;i++) { adj[i].clear(); reach[i] = 0; mindis[i] = 1e18; } for(int i=0;i<M;i++) { adj[x[i]].push_back({y[i], (double)c[i]}); adj[y[i]].push_back({x[i], (double)c[i]}); } dfs(0); if(!reach[H]) return -1; mindis[0] = 0; for(int i=1;i<N;i++) { if(reach[i] && arr[i]==0) { mindis[i] = 0; } } for(int i=0;i<=K;i++) dij(arr); return mindis[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...