제출 #977383

#제출 시각아이디문제언어결과실행 시간메모리
977383faruk사이버랜드 (APIO23_cyberland)C++17
15 / 100
204 ms23572 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define all(a) a.begin(), a.end() using namespace std; const double INF = 1e18; struct edge { double cost; int t; int inc; edge() {} edge(double cost, int t, bool inc) : cost(cost), t(t), inc(inc) { } }; struct node { double cost; int idx, uses; node() {} node(double cost, int idx, int uses) : cost(cost), idx(idx), uses(uses) { } bool operator<(const node &b) const { return cost > b.cost; } }; const int maxK = 50; vector<vector<edge> > graph; vector<int> type; vector<double> pow2(maxK + 1); int n, m, k, h; vector<vector<double> > dijkstra() { int myk = min(k, maxK); vector<vector<double> > dist(n, vector<double>(myk + 1, INF)); dist[h][0] = 0; priority_queue<node> q; q.push(node(0, h, 0)); while (!q.empty()) { node me = q.top(); q.pop(); if (dist[me.idx][me.uses] < me.cost || (me.idx == h and me.uses != 0)) continue; for (auto &[cst, to, typ] : graph[me.idx]) { if (me.uses == myk and typ) continue; double new_cst = cst / pow2[me.uses] + me.cost; if (dist[to][me.uses + typ] > new_cst) { dist[to][me.uses + typ] = new_cst; q.push(node(new_cst, to, me.uses + typ)); } } } return dist; } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { n = N, m = M, k = K, h = H; pow2[0] = 1; for (int i = 1; i <= maxK; i++) pow2[i] = pow2[i - 1] * 2.0; type = arr; graph = vector<vector<edge> > (n); for (int i = 0; i < m; i++) { graph[x[i]].push_back(edge(c[i], y[i], 0)); graph[y[i]].push_back(edge(c[i], x[i], 0)); if (type[i] == 2) { graph[x[i]].push_back(edge(c[i], y[i], 1)); graph[y[i]].push_back(edge(c[i], x[i], 1)); } } vector<vector<double> > dist = dijkstra(); if (*min_element(all(dist[0])) == INF) return -1; double out = *min_element(all(dist[0])); for (int i = 1; i < n; i++) { if (arr[i] == 0) out = min(out, *min_element(all(dist[i]))); } return out; }
#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...