제출 #963126

#제출 시각아이디문제언어결과실행 시간메모리
963126nasir_bashirov사이버랜드 (APIO23_cyberland)C++17
0 / 100
3067 ms61804 KiB
#include "cyberland.h" #include "bits/stdc++.h" using namespace std; #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define pdi pair<long double, int> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define all(x) x.begin(), x.end() #define endl '\n' #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int sz = 1e5 + 5; ll type[sz], n, m, k, h; long double d[sz][31]; vii g[sz]; 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; for(int i = 0; i < M; i++){ g[x[i] + 1].push_back({y[i] + 1, c[i]}); g[y[i] + 1].push_back({x[i] + 1, c[i]}); } for(int i = 1; i <= n; i++){ for(int j = 0; j <= k; j++){ d[i][j] = 1e18; } } priority_queue<pair<pdi, int>, vector<pair<pdi, int>>, greater<pair<pdi, int>>> pq; pq.push({{0.0, 0}, 1}); d[1][0] = 0; for(int i = 1; i < n; i++){ if(arr[i] == 0) pq.push({{0.0, 0}, i + 1}), d[i + 1][0] = 0; } while(!pq.empty()){ int cur = pq.top().second, j = pq.top().first.second; if(d[cur][j] < pq.top().first.first){ pq.pop(); continue; } pq.pop(); for(pii i : g[cur]){ if(d[i.first][j] > d[cur][j] + i.second){ d[i.first][j] = d[cur][j] + i.second; pq.push({{d[i.first][j], j}, i.first}); } if(arr[cur] == 2 and j + 1 <= k and d[i.first][j + 1] > d[cur][j] / 2.0 + i.second){ d[i.first][j + 1] = d[cur][j] / 2.0 + i.second; pq.push({{d[i.first][j + 1], j + 1}, i.first}); } } } long double res = 1e18; for(int i = 0; i <= k; i++){ res = min(res, d[H + 1][i]); } if(res == 1e18) return -1; return res; }
#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...