제출 #967023

#제출 시각아이디문제언어결과실행 시간메모리
967023dubabuba사이버랜드 (APIO23_cyberland)C++17
15 / 100
128 ms38628 KiB
#include <bits/stdc++.h> #include "cyberland.h" #pragma GCC optimize("O3") #pragma GCC target("lzcnt", "popcnt") using namespace std; typedef double dbl; typedef vector<int> vi; typedef long long i64; typedef pair<int, int> pii; #define ff first #define ss second #define MP make_pair const int mxk = 32; const int mxn = 1e5 + 10; vector<pii> adj[mxn]; dbl dis[mxk][mxn]; bool vis[mxn]; int H; template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; } const bool operator < (pair<pair<dbl, int>, int> L, pair<pair<dbl, int>, int> R) { if(L.ff != R.ff) return L.ff < R.ff; if(L.ss == R.ss) return 0; if(L.ss == H) return 1; if(R.ss == H) return 0; return L.ss < R.ss; } const bool operator > (pair<pair<dbl, int>, int> L, pair<pair<dbl, int>, int> R) { if(L.ff != R.ff) return L.ff > R.ff; if(L.ss == R.ss) return 0; if(L.ss == H) return 0; if(R.ss == H) return 1; return L.ss > R.ss; } double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) { ::H = H; for(int i = 0; i < N; i++) adj[i].clear(); for(int i = 0; i < M; i++) { adj[x[i]].push_back(MP(y[i], c[i])); adj[y[i]].push_back(MP(x[i], c[i])); } priority_queue<pair<pair<dbl, int>, int>> pq; for(int i = 0; i < N; i++) for(int j = 0; j <= K && j < mxk; j++) dis[j][i] = -1.0; for(int i = 0; i < N; i++) vis[i] = 0; queue<int> q; vis[0] = 1; q.push(0); pq.push(MP(MP(0.0, 0), 0)); while(q.size()) { int u = q.front(); q.pop(); if(arr[u] == 0) pq.push(MP(MP(0.0, 0), u)); for(pii p : adj[u]) { int v = p.ff; if(!vis[v]) { vis[v] = 1; q.push(v); } } } while(pq.size()) { dbl d = -pq.top().ff.ff; int k = pq.top().ff.ss; int u = pq.top().ss; pq.pop(); if(dis[k][u] > -1.0) continue; if(u == H) return d; dis[k][u] = d; for(pii p : adj[u]) { int v = p.ff; dbl c = p.ss; // cout << " " << v; if(v == 0 || arr[v] == 0) continue; if(dis[k][v] == -1.0) pq.push(MP(MP(-(d + c), k), v)); if(arr[v] == 2 && k < K && k < mxk) if(dis[k + 1][v] == -1.0) pq.push(MP(MP(-(d + c) / 2.0, k + 1), v)); } // cout << endl; } // dbl ans = 1e18; // for(int k = 0; k < mxk; k++) // if(dis[k][H] != -1) // ono_min(ans, dis[k][H]); // if(ans != -1) return ans; return -1; }
#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...