제출 #1253510

#제출 시각아이디문제언어결과실행 시간메모리
1253510anfiCyberland (APIO23_cyberland)C++20
15 / 100
1018 ms1748796 KiB
#include <bits/stdc++.h> using namespace std; const double INF = 1e18; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<vector<pair<int,int>>> adj(N); adj.reserve(N); for (int i = 0; i < M; i++) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } vector<vector<double>> dist(N, vector<double>(K+1, INF)); deque<pair<int,int>> dq; dist[0][0] = 0.0; dq.emplace_front(0, 0); while (!dq.empty()) { auto [u, used] = dq.front(); dq.pop_front(); double d = dist[u][used]; for (auto [v, w] : adj[u]) { double nd = d + w; int nk = used; if (arr[v] == 0) { nd = 0.0; } else if (arr[v] == 2 && used < K) { nd *= 0.5; nk++; } if (nd + 1e-12 < dist[v][nk]) { dist[v][nk] = nd; if (nd < d) dq.emplace_front(v, nk); else dq.emplace_back(v, nk); } } } double ans = INF; for (int k = 0; k <= K; k++) { ans = min(ans, dist[H][k]); } return (ans >= INF/2 ? -1.0 : 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...