제출 #753421

#제출 시각아이디문제언어결과실행 시간메모리
753421Jomnoi사이버랜드 (APIO23_cyberland)C++17
97 / 100
1239 ms57296 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; const int MAX_N = 1e5 + 5; const int MAX_K = 61; const long long INF = 1e18 + 7; vector <pair <int, int>> graph[MAX_N]; double dist[MAX_N][MAX_K]; bool visited[MAX_N]; double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) { K = min(K, 60); for (int i = 0; i < N; i++) { graph[i].clear(); visited[i] = false; for (int k = 0; k <= K; k++) { dist[i][k] = INF; } } for (int i = 0; i < M; i++) { graph[x[i]].emplace_back(y[i], c[i]); graph[y[i]].emplace_back(x[i], c[i]); } queue <int> q; q.push(0); visited[0] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (auto [v, c] : graph[u]) { if (visited[v] == true or v == H) continue; visited[v] = true; q.push(v); } } priority_queue <tuple <double, int, int>> pq; arr[0] = 0; for (int i = 0; i < N; i++) { if (visited[i] == false or arr[i] != 0) continue; pq.emplace(0, 0, i); dist[i][0] = 0; } while (!pq.empty()) { auto [d, k, u] = pq.top(); pq.pop(); if (dist[u][k] < d or u == H) continue; for (auto [v, c] : graph[u]) { if (dist[u][k] + c < dist[v][k]) { dist[v][k] = dist[u][k] + c; pq.emplace(-dist[v][k], k, v); } if (arr[v] == 2 and k < K and (dist[u][k] + c) / 2.0 < dist[v][k + 1]) { dist[v][k + 1] = (dist[u][k] + c) / 2.0; pq.emplace(-dist[v][k + 1], k + 1, v); } } } double res = INF; for (int k = 0; k <= K; k++) res = min(res, dist[H][k]); if (res == INF) res = -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...