제출 #806674

#제출 시각아이디문제언어결과실행 시간메모리
806674TheSahib사이버랜드 (APIO23_cyberland)C++17
15 / 100
3040 ms41336 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define ll long long using namespace std; const ll oo = 1e18; const int MAX = 1e5 + 5; struct edge{ int u, c; }; int n, k, f; int A[MAX]; vector<edge> g[MAX]; bool visited[MAX]; vector<int> starts; void dfs(int node){ visited[node] = 1; for(auto& e:g[node]){ if(visited[e.u]) continue; dfs(e.u); } } double dist[MAX][32]; void dijkstra(){ set<pair<double, pair<int, int>>> st; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { dist[i][j] = oo; } } for(int a:starts){ dist[a][k] = 0; st.insert({a, {a, k}}); } while(!st.empty()){ double d = st.begin()->first; int node = st.begin()->second.first; int l = st.begin()->second.second; st.erase(st.begin()); for(auto& e:g[node]){ double b = d + e.c; if(b < dist[e.u][l]){ st.erase({dist[e.u][l], {e.u, l}}); dist[e.u][l] = b; st.insert({dist[e.u][l], {e.u, l}}); } if(l == 0 || A[e.u] != 2) continue; if(b / 2 < dist[e.u][l - 1]){ st.erase({dist[e.u][l - 1], {e.u, l - 1}}); dist[e.u][l - 1] = b / 2; st.insert({dist[e.u][l - 1], {e.u, l - 1}}); } } } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n = N; k = K; f = H; starts.clear(); for (int i = 0; i < n; i++) { A[i] = arr[i]; g[i].clear(); visited[i] = 0; } 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); starts.push_back(0); for (int i = 0; i < n; i++) { if(visited[i] && A[i] == 0){ starts.push_back(i); } } dijkstra(); double ans = oo; for(int i = 0; i <= k; ++i){ ans = min(ans, dist[f][i]); } if(ans == oo){ return -1; } else{ 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...