제출 #751887

#제출 시각아이디문제언어결과실행 시간메모리
751887aryan12사이버랜드 (APIO23_cyberland)C++17
97 / 100
3044 ms93180 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5, K = 68; double dist[K][N]; vector<pair<int, int> > g[N]; bool vis[N], source[N]; int a[N], H; void dfs(int node) { vis[node] = true; if(a[node] == 0) { source[node] = true; } if(node == H) { return; } for(auto [to, wt]: g[node]) { if(!vis[to]) { dfs(to); } } } double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { H = h; k = min(k, 67); for(int i = 0; i <= n; i++) { source[i] = false; vis[i] = false; if(i != n) a[i] = arr[i]; g[i].clear(); for(int j = 0; j <= k; j++) { dist[j][i] = 1e18; } } for(int i = 0; i < m; i++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } dfs(0); source[0] = true; if(!vis[H]) { return -1; } priority_queue<pair<double, int> > pq; for(int i = 0; i < n; i++) { // cout << "source[i] = " << source[i] << "\n"; if(source[i]) { pq.push({0, i}); dist[0][i] = 0; } } while(!pq.empty()) { auto [dis, p] = pq.top(); pq.pop(); int cur_k = p / 100000, node = p % 100000; dis = -dis; if(dist[cur_k][node] < dis || node == h) { continue; } for(auto [to, wt]: g[node]) { if(a[to] == 0) continue; double wt_d = wt; if(dist[cur_k][to] > dist[cur_k][node] + wt_d) { dist[cur_k][to] = dist[cur_k][node] + wt_d; pq.push({-dist[cur_k][to], to + 100000 * cur_k}); } if(a[to] == 1 || cur_k == k) continue; if(dist[cur_k + 1][to] > (dist[cur_k][node] + wt_d) / 2.0) { dist[cur_k + 1][to] = (dist[cur_k][node] + wt_d) / 2.0; pq.push({-dist[cur_k + 1][to], to + 100000 * (cur_k + 1)}); } } } double ans = 1e18; // for(int i = 0; i < n; i++) // { // for(int j = 0; j <= k; j++) // { // cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << "\n"; // } // } for(int i = 0; i <= k; i++) { ans = min(ans, dist[i][h]); } return ans; }
#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...