제출 #976020

#제출 시각아이디문제언어결과실행 시간메모리
976020nnin사이버랜드 (APIO23_cyberland)C++17
68 / 100
3041 ms15384 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}); } while(!pq.empty()) { auto [dis, u] = pq.top(); pq.pop(); if(u==HH || mindis[u]!=dis) continue; for(auto [v, w]:adj[u]) { if(reach[v] && mindis[v]>dis+w) { mindis[v] = dis+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...